스택, 큐

스택

그냥 후입 선출(Last-in First-out)의 자료구조이다.
파이썬에서는 별도의 모듈을 사용하지 않고 list를 스택으로 활용한다.

구현을 하자면 다음과 같다.

class Stack:
    def __init__(self):
        self.container = list()

    def empty(self):
        if not self.container:
            return True
        else:
            return False

    def push(self, data):
        self.container.append(data)

    def pop(self):
        if self.empty():
            return None
        return self.container.pop()

    def peek(self):
        if self.empty():
            return None
        return self.container[-1]

큐

선입선출을 가지는 자료구조

class Queue:
    def __init__(self):
        self.container = list()
        
    def empty(self):
        if not self.container:
            return True
        else:
            return False

    def enqueue(self, data):
        self.container.append(data)

    def dequeue(self):
        return self.container.pop(0)

    def peek(self):
        return self.container[0]

문제

스택에서 push pop 연산은 맨 뒤에서 일어나서 O(1)인데, queu는 dequeue연산은 맨 앞에서 일어나므로 O(n)을 갖는다.

원형큐

선형의 큐를 원형으로 사용하는 방법

head와 tail을 가리키는 변수를 두어서 데이터를 이동시키는게 아니라 가리키는 변수를 -1함.

class CQueue:
    MAXSIZE = 10
    def __init__(self):
        self.container = [None for _ in range(CQueue.MAXSIZE)]
        self.front = 0
        self.rear = 0

		def is_empty(self):
        return self.front == self.rear:
		def is_full(self):
        return self.front == (self.rear+1)%MAXSIZE:
		def enqueue(self,item):
				if not self.is_full():
					self.rare=(self.rare+1)%MAXSIZE
					self.items[self.rear]=item
		def dequeue():
				if not self.is_empty():
					self.front=(self.front+1)%MAXSIZE
					return self.items[self.front]
		def peek():
				if not self.isEmpty():
					return self.items[(self.front+1)%MAXSIZE]