![[자료구조] Stack & Queue](https://inblog.ai/_next/image?url=https%3A%2F%2Finblog.ai%2Fapi%2Fog%3Ftitle%3D%255B%25EC%259E%2590%25EB%25A3%258C%25EA%25B5%25AC%25EC%25A1%25B0%255D%2520Stack%2520%2526%2520Queue%26logoUrl%3Dhttps%253A%252F%252Finblog.ai%252Finblog_logo.png%26blogTitle%3D%25EB%25B0%25B1%25EC%2597%2594%25EB%2593%259C%25EB%25B8%2594%25EB%25A1%259C%25EA%25B7%25B8-dohyeong&w=1920&q=75)
Stack
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252Fd7421e6c-f9f1-489f-82c2-5d1590daaa93%252FUntitled.png%3Ftable%3Dblock%26id%3Deba9b97b-de49-4cf6-bd1e-d13e43900fb0%26cache%3Dv2&w=3840&q=75)
가장 마지막에 들어간 데이터가 제일 먼저 나오고(LIFO) 가장 먼저 들어간 데이터는 가장 나중에 나온다(FILO)
큐와 더불어 소프트웨어 분야에서매우 중요한 역할을 한다. 자동 메모리가 스택을 기반으로 동작하고 거의 대부분의 네트워크 프로토콜도 스택을 기반으로 구성돰
주요 연산
- 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
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252F3e6c200e-b254-42c4-8f14-5ddde6201156%252FUntitled.png%3Ftable%3Dblock%26id%3D2ddadf9c-24f0-4d20-a592-e8cd4fd31c05%26cache%3Dv2&w=3840&q=75)
먼저 들어간 데이터가 먼저 나오는 (FIFO) 자료구조를 큐라고 한다
스택에서의 삭제는 한쪽에서만 이루어지지만 큐의 경우 삽입(Enqueue)은 Rear 제거(Dequeue) 는 Front에서 수행됨
순환 queue
배열에서의 큐는 삭제를 위해서 Front 하나를 삭제하고 한칸씩 앞으로 옮기는데 비용이 상당히 많이 든다.
이 문제를 해결하기 위해서 Front 와 Rear의 위치를 이동한다
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252F08452475-89c6-4ff7-a56a-00bfc9a61ed3%252FUntitled.png%3Ftable%3Dblock%26id%3Dac1dad73-c279-40c6-a7f2-d53ffef6aa9f%26cache%3Dv2&w=3840&q=75)
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252F16d4b297-95c1-49f9-add1-3450863c84e9%252FUntitled.png%3Ftable%3Dblock%26id%3D50b2113e-5019-49c7-8abc-3a14d4ce4711%26cache%3Dv2&w=3840&q=75)
문제점 발생 → 제거 연산을 수행할 마다 큐의 가용 용량이 줄어든다는 점!!
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252Fec312f80-dfbd-4622-992a-c1e39df096ad%252FUntitled.png%3Ftable%3Dblock%26id%3D245fb800-f544-439d-8bea-3ce41f06429e%26cache%3Dv2&w=3840&q=75)
이 문제를 해결하기 위해서 시작과 끝을 연결해서 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐를
순환 큐(Circular Queue) 라고 한다
공백 상태와 포화 상태
공백이나 포화상태일 때 Front 와 Rear가 같은 위치에 있기 때문에 이 두 상태를 구분해줘야 한다.
- 일반적인 방법 실제 용량보다 1 만큼 더 크게 만들어서 전단과 후단 사이를 비우는 것
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252Fbb8cfcb9-16a7-43c7-b35c-a7da9e6ab6a0%252FUntitled.png%3Ftable%3Dblock%26id%3D345585ea-5292-4701-b9c5-56822a38216d%26cache%3Dv2&w=3840&q=75)
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
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252Fad2bd405-c844-4c0a-ae85-edf587d8965b%252FUntitled.png%3Ftable%3Dblock%26id%3Dc23ae82f-488e-4cc3-b1ad-d3627aa0bd1f%26cache%3Dv2&w=3840&q=75)
포인터를 이용해 연결되므로 삽입 연산을 할 때는 삽입하려는 노드에 후단을 연결하고, 제거할 때는 전단 바로 다음 노드에서 전단에 대한 포인트를 없애기만 하면 됨
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)
Share article