선형 자료구조 - 스택, 큐

1. 스택(Stack)

• LIFO(Last In First Out)
• pop, push, peek, isEmpty 등의 연산이 있다.

1.1 스택의 함수

1.1.1 pop

• 스택 구조에서 가장 나중에 추가된 원소를 빼내서 반환
• 비어있는 스택에서 pop연산을 할 경우 stack underflow가 발생

1.1.2 push

• 스택의 구조의 맨 뒤에 원소를 추가

1.1.3 peek

• 스택의 top의 가장 맨 위의 요소를 반환

1.1.4 size

• 스택의 현재 크기를 반환

1.1.5 isEmpty

• 스택이 비어있으면 True(1), 그렇지 않으면 False(0) 반환

1.3 구현

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

  def isEmpty(self):
    if item:    
      return 0
    else:
      return 1

  def push(self, item):
    if item:    
      self.items.append(item)
      
  def push(self):
    if item:    
      self.items.pop(item)
      
  def peek(self):
    return self.items[-1]

  def size(self):
    if item:    
      return len(self.items)

myStack = stack()
myStack.isEmpty()	# 1
myStack.push(1)		
myStack.push(2)
myStack.push(3)
myStack.peek()		# 3
myStack.size()		# 3

print(myStack.pop())	# 3
print(myStack.pop())	# 2
print(myStack.pop())	# 1

2. 큐(Queue)

• FIFO(First In First Out)
• 삭제만 수행되는front과 삽입만 수행되는 rear를 통해 큐의 상태를 표현

2.3 큐의 함수

2.3.1 enQueue

• rear부분에 원소를 추가

1.1.2 dequeue

• front부분의 원소 제거 후 반환

1.1.3 isEmpty

• 큐가 비어있으면 True(1), 그렇지 않으면 False(0) 반환

1.1.4 size

• 큐의 현재 크기를 반환

1.3 선형 큐 구현

class queue:
  def __init__(self):
    self.items = []
    #self.front = 0
    #self.rear = 0

  def isEmpty(self):
    if item:    
      return 0
    else:
      return 1

  def enqueue(self, item):
    if item:    
      self.items.append(item)
      
  def dequeue(self):
    if item:    
      tmp = self.items.pop(0)
      return tmp

  def size(self):
    if item:    
      return len(self.items)

myStack = queue()
myStack.isEmpty()	# 1
myStack.enqueue(1)		
myStack.enqueue(2)
myStack.enqueue(3)
myStack.size		# 3

print(myStack.dequeue())	# 1
print(myStack.dequeue())	# 2
print(myStack.dequeue())	# 3

• 파이썬으로 구현하게 되면 리스트의 크기를 알아서 조절해주기 때문에 front == rear인 상황은 항상 큐가 비어있는 상태이다 하지만 C언어를 이용해 구현할 경우 항상 비어있는 상태는 아니다.

  
  
  

1.4 원형 큐 구현

SIZE = 5 # 큐 사이즈 제한
class queue:
  def __init__(self):
    self.items = [None] * SIZE
    self.front = 0
    self.rear = 0

  def isEmpty(self):
    if self.front == self.rear:    
      return 1
    else:
      return 0
      
   def isFull(self):
    if self.front == (self.rear + 1) % SIZE:    
      return 1
    else:
      return 0

  def enqueue(self, item):
    if self.isFull() != 1:    
      self.rear = (self.rear + 1) % SIZE
      self.item[self.rear] = item
      
  def dequeue(self):
    if self.isEmpty != 1:  
      tmp = item[self.front]
      self.front = (self.front + 1) % SIZE
      return tmp

  def size(self):
    if item:    
      return (self.rear - self.front + SIZE) % SIZE

myStack = queue()
myStack.isEmpty()	# 1
myStack.enqueue(1)		
myStack.enqueue(2)
myStack.enqueue(3)
myStack.size		# 3

print(myStack.dequeue())	# 1
print(myStack.dequeue())	# 2
print(myStack.dequeue())	# 3

출처

• https://devuna.tistory.com/22
• https://mailmail.tistory.com/33
• https://velog.io/@changyeonyoo/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0python-%EC%9B%90%ED%98%95%ED%81%90-%EB%8D%B1-CircularQueue-CircularDeque-%EA%B5%AC%ED%98%84