[자료구조] Stack & Queue

Stack

큐와 더불어 소프트웨어 분야에서매우 중요한 역할을 한다. 자동 메모리가 스택을 기반으로 동작하고 거의 대부분의 네트워크 프로토콜도 스택을 기반으로 구성돰

주요 연산

• push

• pop

배열기반 스택

링크드 리스트기반 스택

파이썬 클래스를 이용한 스택 구현

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self,data):
        self.items.append(data)
    
    def pop(self):
        if not self.isEmpty() :
            data = self.items[-1]
            del self.items[-1]
            return data
        else:
            print('stack empty')
    
    def peek(self):
        return self.items[-1]
    
    def isEmpty(self):
        if len(self.items) > 0:
            return False
        else: 
            return True

Queue

스택에서의 삭제는 한쪽에서만 이루어지지만 큐의 경우 삽입(Enqueue)은 Rear 제거(Dequeue) 는 Front에서 수행됨

순환 queue

문제점 발생 → 제거 연산을 수행할 마다 큐의 가용 용량이 줄어든다는 점!!

공백 상태와 포화 상태

공백이나 포화상태일 때 Front 와 Rear가 같은 위치에 있기 때문에 이 두 상태를 구분해줘야 한다.

• 일반적인 방법 실제 용량보다 1 만큼 더 크게 만들어서 전단과 후단 사이를 비우는 것

class CircularQueue:
    queueSize = 10

    def __init__(self):
        self.front = 0
        self.rear = 0
        self.queue = [None]*self.queueSize 
    
    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear +1) % self.queueSize
    
    def enqueue(self,data):
        if self.isFull():
            print("Full")
            return
        self.rear = (self.rear + 1) %(self.queueSize)
        self.queue[self.rear] = data
    
    def dequeue(self):
        if self.isEmpty():
            print("EMPTY")
            return 
        self.front = (self.front +1 ) % self.queueSize
        return self.queue[self.front]

링크드 queue

포인터를 이용해 연결되므로 삽입 연산을 할 때는 삽입하려는 노드에 후단을 연결하고, 제거할 때는 전단 바로 다음 노드에서 전단에 대한 포인트를 없애기만 하면 됨

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

class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.count = 0

    def is_empty(self):
        return self.front is None

    def enqueue(self, new_node):
        if self.front is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next_node = new_node
            self.rear = new_node
        self.count += 1

    def dequeue(self):
        if self.front is None:
            return None
        front_node = self.front
        if self.front.next_node is None:
            self.front = None
            self.rear = None
        else:
            self.front = self.front.next_node
        self.count -= 1
        return front_node

def create_node(new_data):
    return Node(new_data)

def destroy_node(node):
    pass

def create_queue():
    return LinkedQueue()

def destroy_queue(queue):
    while not queue.is_empty():
        popped = queue.dequeue()
        destroy_node(popped)