💡 가장 마지막에 들어간 데이터가 제일 먼저 나오고(LIFO) 가장 먼저 들어간 데이터는 가장 나중에 나온다(FILO)
큐와 더불어 소프트웨어 분야에서매우 중요한 역할을 한다. 자동 메모리가 스택을 기반으로 동작하고 거의 대부분의 네트워크 프로토콜도 스택을 기반으로 구성돰
스택 생성 초기에 사용자가 부여한 용량만큼 생성해야 한다.
배열과 달리 인덱스를 활용한 노드 접근이 불가능함
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
스택에서의 삭제는 한쪽에서만 이루어지지만 큐의 경우 삽입(Enqueue)은 Rear 제거(Dequeue) 는 Front에서 수행됨
배열에서의 큐는 삭제를 위해서 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]
포인터를 이용해 연결되므로 삽입 연산을 할 때는 삽입하려는 노드에 후단을 연결하고, 제거할 때는 전단 바로 다음 노드에서 전단에 대한 포인트를 없애기만 하면 됨
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)
잘 읽었습니다. 좋은 정보 감사드립니다.