[Python] Stacks

• 스택의 구조

기본적으로 스택은 넣을 때는 한쪽 끝에서 밀어넣어야 하고(push), 꺼낼 때에는
같은 쪽으로 뽑아 꺼내야한다.(pop) 간단히 그림으로 나타내면 다음과 같다.

이와 비슷한 선형 자료구조 큐(Queue)는 좀 다르다. 큐는 '선입선출'의 구조로서,
먼저 들어간 요소가 가장 먼저 나오는 구조이다. 기본적으로 스택은 한쪽에서 꺼내고
빼고를 하는 반면, 큐는 한쪽으로 들어가면 다른쪽에서 나온다! 그리고 스택은 가장
마지막에 들어간 가장 먼저 나온다. (후입선출)

스택에는 정해진 저장 공간이 있다. 따라서 비어있는 스택에서 원소를 꺼내려 하거나,
꽉찬 스택에 데이터 원소를 넣으려고 할 때 문제가 발생한다. 이러한 문제들을 각각
Stack underflow, Stack overflow라고 칭한다.

• 스택의 연산 및 구현

스택의 연산에는 총 5가지가 있다. 각각은 다음과 같다.

• Size: 현재 스택에 들어있는 원소의 수를 반환
• isEmpty(): 현재 스택이 비어있는지를 판단
• push(x): 데이터 원소 x를 스택에 추가
• pop(): 스택의 맨 위에 저장된 원소를 제거 (맨 마지막에 들어온게 맨 먼저 나옴)
• peek(): 스택의 꼭대기(맨 마지막으로 push된, 앞으로 pop의 대상이 되는) 원소를 반환

이들은 각각 Python의 배열과 양방향 연결리스트로 구현될 수 있다.

#python의 리스트로 스택 구현하기

class ArrayStack:

	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]

양방향 연결리스트로도 동일한 작업을 수행할 수 있다.

# 양방향 연결리스트 정의
class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None # 양방향으로 연결된 모습

class DoublyLinkedList:
    def __init__(self, item):
        self.nodeCount = 0
        self.head = None(None)
        self.tail = None(None)

        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

# 양방향 연결리스트로 스택 구현
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 = None(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