[자료구조] 스택, 큐, 원형 리스트 (in python)

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의  "자료구조", 이현자 교수님

스택(Stack)

1. 스택이란 ?

• 후입선출 = Last In First Out = LIFO
• 스택 연산 : push(데이터 넣고), pop(데이터 빼고)
• 사용 예시
  • 시스템 스택
    • 함수 호출을 관리하는 스택으로 운영체제가 사용하는 스택
    • 복귀할 주소를 기억하는데 사용
    • 컴퓨터 실행시에 이전으로 돌아가기 기능을 사용하면 가장 최근에 실행했던 내용을 삭제해주는 것과 같은 이치
      -> 가장 최근에 실행했던 내용을 삭제하고 바로 이전의 상태로 돌아갈 수 있는 복귀할 주소를 기억
  • 스택 프레임 (= 활성 레코드)
    • 시스템 스택의 top에 스택프레임이 push
      = 함수가 호출될 때마다(새로운 프로그램이 or 동작이 실행될 때마다) 스택 프레임이 만들어지고 스택프레임에 추가되는 것
    • 지역변수, 리턴 어드레스, 복귀주소 등이 저장

2. 스택 구현

(1) 기본 구현 : 파이썬이 아닌 언어에서의 구현

• top 변수 : 스택 내 가장 최근에 추가된 값의 인덱스를 담는 변수
• top 변수를 이용하여 값을 push, pop 실행
• top을 이용해서만 스택의 값에 접근 가능
• 빈스택일 때는 top = -1
• push할 때는 top을 먼저 증가 후 삽입 <-> pop할 때는 먼저 삭제 후 top을 감소

class stack:
  def __init__(self, size):
      self.size = size
      self.top = -1 
      	# 빈스택일 때(초기값) = -1
      self.stack = [None] * size

  def viewstack(self):
      print(self.stack)

  def push(self,item):
      if self.top < self.size - 1: 
      	# top은 인덱스값이기 때문에 size-1일때가 최대
        	-> 값을 추가하기 위해서는 한칸은 비어 있어야 함
            -> top < size - 1이 full이 아닐 조건이 되는 것
          self.top += 1
          	# top은 이미 추가되어 있는 인덱스를 가리킴
            	-> top을 먼저 증가시켜줘야 top의 값이 push할 데이터의 위치를 가리킬 수 있음
          self.stack[self.top] = item
          	# stack 리스트의 top 위치에 item 값 push
      else: print("stack is full")

  def pop(self):
      temp = 0 
      	# 몇 번째 값이 삭제되었는지 확인하기 위한 변수
      if self.top > -1: 
      	# stack이 비어있지 않으면
          temp = self.top
          	# temp에 현재의 top값을 할당
          self.stack[self.top] = None
          	# pop을 할 때는 top이 가리키는 값을 먼저 삭제 후 top값 변경
          self.top -= 1
          return temp
      else: print('stack is empty')

s = stack(5)
for i in [2,3,4,5,6,7]:
    print(f"{i-1}번째 push")
    s.push(i)
    s.viewstack()
    print()

for i in range(6):
    print(f"{i + 1}번째 pop")
    s.pop()
    s.viewstack()
    print()

<결과>

(2) 파이썬 구현

• top 변수 필요 없음
• 인덱스를 이용하여 값을 push, pop하는 것이 아니라 내장함수를 사용
• push는 list.append()를 사용
• pop은 list.pop()을 사용

class stack:
  def __init__(self, size):
    self.size = size
    self.stack = []

  def viewstack(self):
    print(self.stack)

  def push(self,item):
    if len(self.stack) < self.size:
      self.stack.append(item)
    else: print("stack is full")

  def pop(self):
    temp = 0
    if not self.stack:
      print('stack is empty')
    else: return self.stack.pop()

s = stack(5)
for i in [2,3,4,5,6,7]:
    print(f"{i-1}번째 push")
    s.push(i)
    s.viewstack()
    print()

for i in range(6):
    print(f"{i + 1}번째 pop")
    s.pop()
    s.viewstack()
    print()

<결과>

 

---

큐(Queue)

1. 큐란 ?

• 선입선출 = First-In-First-Out = FIFO
• 큐 연산: enqueue(데이터 넣고), dequeue(데이터 빼고)
• 사용 예시
  • 프린터, 컴퓨터 사이 인쇄 작업
  • 대기열 (은행, 공항 등등)

2. 큐 구현

(1) 기본 구현

• front, rear : 큐의 인덱스
  • front : 큐의 첫 데이터가 시작되는 곳보다 한 칸 앞을 가리키는 인덱스
    -> 가장 최근에 삭제된 데이터의 인덱스 (dequeue에 사용)
  • rear : 가장 최근에 추가된 데이터의 인덱스 (enqueue에 사용)
  • empty 조건
    : front == rear
    -> rear는 가장 최근에 추가된 데이터 인덱스 & front는 가장 최근에 삭제된 데이터 인덱스
    -> 삽입이 되어야 삭제가 가능
    -> 삽입이 삭제보다 선행조건으로 이해 가능
    -> 결국 이 조건은 가장 최근에 삽입된 데이터가 삭제되었다로 이해 가능
  • full 조건
    : self.rear == self.size - 1
    -> 큐의 최대 인덱스는 self.size - 1
    -> 가장 최근에 추가된 데이터의 인덱스가 큐의 최대 인덱스와 같다면 해당 큐는 full
  • enqueue : rear += 1 -> 삽입
  • dequeue : front += 1 -> 삭제

class Queue:
  def __init__(self, size):
    self.size = size
    self.queue = [None] * size
    self.front = -1
    self.rear = -1
  
  def isEmpty(self): 
    return self.front == self.rear
    	# 큐의 리스트가 비었다면 참을 반환
  
  def isFull(self):
    return self.rear == self.size - 1
     # 큐의 리스트가 모두 찼다면 참을 반환
  
  def enqueue(self, item):
    if not self.isFull(): 
      self.rear += 1
      	# rear는 최근에 추가된 데이터의 위치를 담고 있으므로 rear + 1 위치에 데이터를 삽입해야 함
        	-> 삽입 전에 rear += 1 
      self.queue[self.rear] = item
      	# +1 해준 rear값의 위치에 item을 추가
    else: print('Queue full')
  
  def dequeue(self):
    #temp = 0
    if not self.isEmpty():
      self.front += 1
      	# front는 최근에 삭제된 데이터의 위치를 담고 있으므로 front + 1 위치의 데이터를 삭제해야 함
      #temp = self.queue[self.front]
      self.queue[self.front] = None
      	 # +1 해준 front값의 위치에 있는 값을 삭제 = None으로 변경
      #return temp
    else: print('Queue empty')
  
  def view(self):
    print(self.queue)
    print('rear = %d front = %d' %(self.rear, self.front))
  
q = Queue(5) 
for i in [2,3,4,5,6,7]:
    print(f"{i-1}번째 enqueue")
    q.enqueue(i)
    q.view()
    print()

for i in range(6):
    print(f"{i + 1}번째 dequeue")
    q.dequeue()
    q.view()
    print()
  

<결과>

3. 큐의 한계점

• 삭제, 삽입 연산이 진행됨에 따라 큐의 오른쪽으로 front, rear가 몰리게 됨
• full의 조건을 rear == size - 1로 두었을 때, 이 조건을 만족하더라도 full이 아닐 가능성
  WHY? )
  rear와 front는 개별적으로 값이 움직인다. rear는 삽입에만 사용되고 front는 삭제에만 사용된다. rear가 enqueue 연산을 계속 진행하다 size - 1에 도달하면 full의 조건을 만족한다. 그러고 난 뒤, 다 채워진 큐에 삭제 연산을 계속하다 보면 사실상 비어있는 큐가 되는데 그럼에도 rear값은 계속 size - 1과 동일하기 때문에 full로 취급되어 enqueue 연산이 실행되지 못한다

=> 이 한계점 해결하기 위해 원형큐를 사용한다

 

---

원형 큐(Circle Queue)

1. 원형 큐란 ?

• 선형 큐의 한계점을 해결할 수 있는 자료구조
• rear가 리스트의 마지막 인덱스를 가리키고 그 앞의 데이터들이 삭제되었을 때 앞의 빈공간들에 다시 데이터 삽입이 가능하도록 함
  cf) 일반 큐는 앞의 데이터들이 삭제되었어도 앞의 빈공간들에 다시 데이터 삽입 불가
• 큐의 모든 칸을 전부 채우지 않고 한 칸은 남겨두고 사용
  -> 이유는 full, empty 조건 설정을 위해

2. 원형 큐 구현

(1) 기본 구현

• (self.rear + 1) % self.size를 이용하여 인덱스 값 설정
  • 이유 1 : front, rear는 인덱스이기 때문에 범주를 넘어서서는 안됨
    -> rear, front는 계속 증가하는데 이를 리스트 인덱스 범주 내에 위치하게 하기 위함
  • 이유 2 : 배열의 첫 인덱스부터 다시 데이터의 삽입을 가능하게 하기 위해
• 위처럼 인덱스 값 설정의 방식이 다른 것을 제외하고는 일반 큐의 기본 구현과 차이 없음

class CQueue:
  def __init__(self, size):
    self.front = 0
    self.rear = 0
    self.size = size
    self.cqueue = [None] * self.size
    self.count = 0

  def enqueue(self, item):
    if not self.isFull():
      self.rear = (self.rear + 1) % self.size
      self.cqueue[self.rear] = item
      self.count += 1
    else:
      print("Queue full")
  
  def dequeue(self):
    if not self.isEmpty():
      self.front = (self.front + 1) % self.size
      #item = self.cqueue[self.front]
      self.cqueue[self.front] = None
      self.count -= 1
      #return item
    else:
      print("Queue Empty")
  
  def view(self):
    print(self.cqueue)
    print(f'rear = {self.rear}, front = {self.front}')
  
  def isEmpty(self):
    return self.front == self.rear
  
  def isFull(self):
    return self.front == (self.rear + 1) % self.size
    
q = CQueue(5)
q.view()

print()
print('--------------------------------------------')
print('[Enqueue 시작]')
for i in range(6):
  print(f'[{i+1}번째 enqueue]')
  q.enqueue(i)
  q.view()
  print()
  
print()
print('--------------------------------------------')
print('[Dequeue 시작]')
for i in range(6):
  print(f'[{i+1}번째 dequeue]')
  q.dequeue()
  q.view()
  print()

<결과>

 

(2) 파이썬 구현

• 파이썬에서의 리스트 함수를 사용하여 큐를 구현하면 무조건 원형 큐로 구현 됨
• front, rear 필요 없음
• 스택과 동일하게 append(), pop()을 이용하여 enqueue, dequeue 실행

class Queue:
  def __init__(self, size):
    self.size = size
    self.queue = []

  def isFull(self):
    return self.size == len(self.queue)
  
  def isEmpty(self):
    return not self.queue
  
  def enqueue(self, item):
    if not self.isFull():
      self.queue.append(item)
    else: print("Queue Full")
  
  def dequeue(self):
    if not self.isEmpty():
      self.queue.pop(0)
    else: print("Queue Empty")
  
  def view(self):
    print(self.queue)

q = Queue(5)
for i in [2,3,4,5,6,7]:
    print(f"{i-1}번째 enqueue")
    q.enqueue(i)
    q.view()
    print()

for i in range(6):
    print(f"{i + 1}번째 dequeue")
    q.dequeue()
    q.view()
    print()

<결과>