[자료구조] 스택과 큐 (Stack & Queue)

스택(Stack)

 

스택은 후입선출(LIFO, Last In First Out) 방식으로 새로 들어오는 데이터는 저장소의 끝 부분이고, 내보내는 데이터도 끝 부분입니다.

 

• Push (삽입)
  
  새로운 데이터를 가장 끝에 삽입합니다
  
  
• Pop (추출)
  
  가장 끝의 데이터를 삭제합니다
  
  
  
• Peek (읽기)
  
  스택에서 끝의 데이터를 읽습니다
  
  

class Node:
    def __init__(self, data):
        self.next = None
        self.data = data


class Stack:
    def __init__(self):
        self.__top = None

    def push(self, data):
        if self.__top is None:
            self.__top = Node(data)
        else:
            new_node = Node(data)

            p = self.__top
            while p.next is not None:
                p = p.next

            p.next = new_node

    def pop(self):
        p = self.__top
        while p.next.next is not None:
            p = p.next

        data = p.next.data
        p.next = None

        return data

    def peek(self):
        p = self.__top
        while p.next is not None:
            p = p.next

        return p.data


stack = Stack()

stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print(stack.pop())
print(stack.peek())

파이썬으로 구현한 스택입니다. 연결리스트를 이용하여 구현했습니다.

큐 (Queue)

 

큐는 선입선출(FIFO, First In First Out) 방식으로 새로 들어오는 데이터는 저장소의 끝 부분, 내보내는 데이터는 저장소의 첫 부분입니다.

 

 

• Front
  
  큐의 첫 원소를 의미합니다
  
  
• Rear (큐의 끝 원소)
  
  큐의 끝 원소를 의미합니다.
  
  
  
• EnQueue
  
  큐의 Rear에서 이루어지는 삽입연산입니다.
  
  
• DeQueue
  
  큐의 Front에서 이루어지는 삭제연산입니다

 

class Node:
    def __init__(self, data):
        self.next = None
        self.data = data


class Queue:
    def __init__(self):
        self.__front = None
        self.__rear = None

    def enqueue(self, data):
        if self.__front is None:
            self.__front = Node(data)
            self.__rear = self.__front
        else:
            new_node = Node(data)
            self.__rear.next = new_node
            self.__rear = self.__rear.next

    def dequeue(self):
        data = self.__front.data
        self.__front = self.__front.next
        return data


queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.dequeue()

파이썬으로 구현한 큐입니다. 마찬가지로 연결리스트를 이용하여 구현했습니다.