스택(Stack) in Python

[ 스택이란? ]

- 자료를 보관할 수 있는 선형 구조. 한쪽 끝에서 밀어넣고(push) 같은 쪽에서부터 뽑아쓴다.(pull)

- 후입선출(LIFO - Last In, First Out)

 

[ 스택 언더플로우 & 스택 오버플로우 ]

- 스택 언더플로우(stack underflow): 비어있는 스택에서 데이터 원소를 꺼내려고 할 때 발생하는 에러

- 스택 오버플로우(stack overflow): 꽉 찬 스택에 데이터 원소를 넣으려 할 때 발생하는 에러

 

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

1. 구현 방법

 1) 배열 이용 - Python의 리스트와 메서드를 이용하여 스택을 구현한다.

 2) 연결리스트 이용 - 양방향 연결리스트를 이용하여 스택을 구현한다.

 

2. 연산의 정의

 1) size() - 현재 스택에 들어있는 데이터 원소의 수 

 2) isEmpty() - 현재 스택이 비어 있는지 판단 //스택 언더플로우 방지

 3) push(x) - 데이터 x를 스택에 추가

 4) pop() - 스택의 맨 위에 저장된 데이터 원소 제거 and 반환

 5) peek() - 스택의 맨 위에 저장된 데이터 원소 반환 (제거X)

 

[ 배열로 구현한 스택 ]

 

class ArrayStack:
    def __init__(self): #빈 리스트 초기화
        self.data = []
    def size(self): #스택의 크기 반환
        return len(self.data)
    def isEmpty(self): #스택이 비어있는지 판단 (True/False)
        return self.size()==0
    def push(self, item): #데이터 원소를 맨 끝에 추가
        self.data.append(item)
    def pop(self): #데이터 원소 삭제 및 반환
        return self.data.pop() 
    def peek(self): #스택의 꼭대기 원소 반환
        return self.data[-1] 

 

[ 양방향 리스트로 구현한 스택 ]

 

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList # 클래스 import

class LinkedListStack:
    def __init__(self):
        self.data = DoublyLinkedList() #비어있는 양방향 리스트로 초기화
    
    def size(self):
        return self.data.getLength()
        
    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

해당 클래스는 pythonds.vasic.stack 에서 Stack을 im port하여 사용가능하다.