스택(Stack)
자료 (data element)를 보관할 수 있는 선형 데이터 구조.
마치 접시를 차곡차곡 쌓았다가 맨 위의 접시부터 다시 꺼내어 사용하는 것처럼, 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조이다.
스택에 데이터를 추가하는 (집어넣는) 동작을 push연산이라 하고, 마지막에 추가되었던 원소를 참조하고 삭제하는 (꺼내는) 동작을 pop연산이라고 한다.
예를 들어, 컴퓨터 내부에서 프로그램이 실행할 때 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출된 곳으로 돌아가는 동작을 구현하는 데에도 스택이 이용된다.
스택의 추상적 자료구조 구현
(1) 배열(array)을 이용하여 구현
- Python 리스트와 메서드들을 이용
(2) 연결 리스트(linked list)를 이용하여 구현
- Doubly linked 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, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
Doubly linked list로 구현한 스택
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
Comments