Post

[자료구조] 8. 스택 (Stacks)

Posted
By Jihyun,Ryu 3 min read

스택 (Stacks)

  • 스택이란 자료를 순차적으로 보관할 수 있는 선형구조이다.

    • 스택은 후입선출(LIFO, Last-In First-Out)형식의 구조를 가지고 있다.
      • 후입선출: 가장 최근에 들어온 데이터가 가장 먼저 나가는 데이터 관리 방식이다.
      • 후입선출 구조를 수행하기위해 스택은 push, pop을 통해 데이터를 관리한다.

    • push: 스택에 데이터를 추가


    • pop: 스택에서 가장 최근에 추가된 데이터를 제거


    • 스택에서는 다음과 같은 오류가 발생할 수 있다.
      • Stack Underflow: 꺼낼 데이터가 없는데 꺼내려고 시도할 때 발생하는 오류
      • Stack Overflow: 스택이 꽉차 있는 상태에서 데이터 원소를 넣으려고 시도할 때 발생하는 오류


스택의 추상적 자료구조 구현

(1) 연산의 정의

  • size(): 스택에 들어있는 데이터 원소의 수를 구한다.
  • isEmpty(): 스택이 비어있는지 확인한다.
  • push(x): 스택에 데이터 원소 x를 스택에 추가한다.
  • pop(): 스택의 맨 위에 저장된 데이터 원소를 제거하고 반환한다.
  • peek(): 스택의 맨 위에 저장된 데이터 원소가 무엇인지 확인한다.


(2) 배열(Array)를 이용하여 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class ArrayStack:

    def __init__(self):
            self.data = [] # 빈 스택을 초기화

    def size(self):
            return len(self.data) # 스택의 크기를 리턴

    def isEmpty(self):
            return self.size()==0 # 스택이 비어 있는지 판단

    def push(self, item):
            self.data.append(item) # 데이터 원소를 추가 

    def pop(self):
            self.data.pop() # 데이터 원소를 삭제 (리턴)

    def peek(self):
            return self.data[-1] # 스택의 꼭대기 원소 반환


(3) 양방향 연결리스트 (Doubly Linked List)를 이용하여 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 노드, 양방향연결리스트의 모듈 코드는 이전 포스팅을 참고 부탁드립니다.
from utils_practice.node_v2 import Node
from utils_practice.linkedlist_v2 import DoublyLinkedList

class LinkedListStack:

    def __init__(self):
        self.data = DoublyLinkedList() # 빈 스택을 초기화
    
    def size(self):
        return self.data.nodeCount # 스택의 크기를 리턴
    
    def isEmpty(self):
        return self.size() == 0 # 스택이 비어 있는지 판단
    
    def push(self, item):
        node = Node(item)
        self.data.insertAt(self.size() + 1, node) # 데이터 원소를 추가
    
    def pop(self):
        return self.data.popAt(self.size()) # 데이터 원소를 삭제 (리턴)
    
    def peek(self):
        return self.data.getAt(self.size()).data # 스택의 꼭대기 원소 반환


(4) 파이썬 라이브러리

  • 스택은 굉장히 많이 사용되는 알고리즘이기에 파이썬 라이브러리 형태로도 존재한다.

    1

      from pythonds.basic.stack import Stack


References

Data, Data Structure
Data Data Structure Stacks ADT
This post is licensed under CC BY 4.0 by the author.