스택(Stacks)

스택

특정한 문제를 풀기에 적합한 알고리즘을 구현하는데 이용되는 자료구조이다.

스택은 자료(data element)를 보관할 수 있는 (선형) 구조이다. 단, 스택에서는 데이터를 넣을 때에는 한 쪽에서 밀어 넣어야하고(push연산) 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야하는(pop연산) 제약이 있다.

스택은 후입선출(LIFO : Last-In First-out)의 특징을 가지는 선형 자료구조이다.

 

 

스택의 동작

 

 

 

 

스택에서 발생하는 오류

• 비어있는 스택에서 데이터 원소를 꺼내려 할 때 -> 스택 언더플로우(stack underflow)
• 꽉 찬 스택에 데이터 원소를 넣으려 할 때 -> 스택 오버플로우(stack overflow)

 

 

 

 

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

1. 배열(array)을 이용하여 구현

• python 리스트와 메서드들을 이용

2. 연결 리스트(listed list)를 이용하여 구현

• 미리 구현해둔 양방향 연결 리스트 이용

 

 

 

연산의 정의

• size() : 현재 스택에 들어있는 데이터 원소의 수를 구함
• isEmpty() : 현재 스택이 비어 있는지를 판단
• push(x) : 데이터 원소 x를 스택에 추가
• pop() : 스택의 맨 위에 저장된 데이터 원소를 제거 (또는 반환)
• peek() : 스택의 맨 위에 저장된 데이터 원소를 반환 (제거하지 않음)

 

 

 

파이썬 리스트로 스택 구현하기

class ArrayStack:
    # 빈 스택을 배열로 초기화
    def __init__(self):
        self.data = [] 
        
    # 스택의 크기
    def size(self):
        return len(self.data)
    
    # 빈 스택 판단 여부
    def isEmpty(self):
        return self.size() == 0
    
    # 데이터 원소 추가
    def push(self, itme):
        self.data.append(item)
        
    # 데이터 원소 삭제 (리턴)
    def pop(self):
        return self.data.pop()
    
    # 스택의 꼭대기 원소 반환
    def peek(self):
        return self.data[-1]

 

 

 

양방향 연결 리스트로 스택 구현하기

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

 

 

 

참고

from pythons.basic.stack import Stack

S = Stack() 스택 초기화

dir(S) 제공하는 메서드들 확인