[자료구조] 스택(Stack) 개념 및 코드 구현

 

 

 

 

 

자료구조 중 하나인 스택(Stack)에 대해 알아보고, 직접 코드로 구현해보자.

배열 구현과 연결 리스트 구현 모두 해볼 것이다.

들어가자.

 

 

 

 

 

 

스택(Stack) 개념

---

 

가장 나중에 넣은 데이터를 가장 먼저 빼내는 데이터 구조.

LIFO(Last In First Out) 방식.

스택의 가장 위 요소를 Top이라 한다.

 

 

 

 

 

 

 

활용

재귀적으로 함수를 호출해야 하는 작업에서, 임시 데이터를 스택에 쌓아두고 이전 단계로 돌아갈 때 데이터를 다시 꺼내오는 등으로 쓰인다.

 

 

기능

1. push()

: 스택의 원소를 추가한다.

2. top()

: 스택의 가장 위 원소를 가져온다.

3. pop()

: 스택의 가장 위 원소를 뽑아낸다.

4. isEmpty()

: 스택의 empty 여부를 확인한다.

 

 

 

 

 

스택(Stack) 구현

---

 

배열 구현

 

class stacking:

  def __init__(self):
    self.top = []
  
  def push(self, a):
    self.top.append(a)
  
  def pop(self):
    if self.isEmpty():
      return print('Stack is Empty')
    else:
      return self.top.pop()
  
  def isEmpty(self):
    if len(self.top) > 0:
      return False
    else:
      return True

  def ttop(self):
    if self.isEmpty():
      return print('Stack is Empty')
    else:
      return self.top[-1]

 

 

 

 

 

 

연결 리스트 구현

 

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

class LinkedlistStack:
  def __init__(self):
    self.head = None
  
  def push(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
  
  def pop(self):
    pop_object = None
    if self.head is None:
      return print('Stack is Empty')
    else:
      pop_object = self.head.data
      self.head = self.head.next
      return pop_object

  def top(self):
    top_object = None
    if self.head is None:
      return print('Stack is Empty')
    else:
      top_object = self.head.data
      return top_object

  def isEmpty(self):
    isEmpty = False
    if self.head is None:
      isEmpty = True
    else:
      isEmpty = False
    return isEmpty