[자료구조] Stack & Queue

Aug 17, 2023

Contents

Stack 주요 연산 배열기반 스택 링크드 리스트기반 스택 파이썬 클래스를 이용한 스택 구현 Queue 순환 queue 링크드 queue

Stack

💡

가장 마지막에 들어간 데이터가 제일 먼저 나오고(LIFO) 가장 먼저 들어간 데이터는 가장 나중에 나온다(FILO)

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

주요 연산

push

배열기반 스택

스택 생성 초기에 사용자가 부여한 용량만큼 생성해야 한다.

링크드 리스트기반 스택

배열과 달리 인덱스를 활용한 노드 접근이 불가능함

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


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

💡

먼저 들어간 데이터가 먼저 나오는 (FIFO) 자료구조를 큐라고 한다

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

순환 queue

배열에서의 큐는 삭제를 위해서 Front 하나를 삭제하고 한칸씩 앞으로 옮기는데 비용이 상당히 많이 든다.

이 문제를 해결하기 위해서 Front 와 Rear의 위치를 이동한다

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

이 문제를 해결하기 위해서 시작과 끝을 연결해서 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐를

순환 큐(Circular 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)