Stack and Queues(1) : Stacks

Stacks and queues

• Stack : 가장 최근(마지막)에 추가된 아이템을 확인하는 자료구조
• Queue : 가장 처음에 추가된 아이템을 확인하는 자료구조

 

Client, implementation, interface

 

Stack API

• Stack과 관련된 아주 기본적인 method입니다.
  • stack에 아이템을 추가하는 push, 마지막 아이템을 제거하며 반환하는 pop, stack이 비었는지 확인하는 isEmpty 등이 있습니다.
  • 물론 Java 기준이기 때문에 Python과 약간의 차이는 있지만 LIFO 구조 자체는 동일합니다.

 

Stack test client

• 아주 간단한 stack 예제 입니다.
  문자열이 '-'과 동일할 땐 pop하며 출력, 그렇지 않을 땐 stack에 추가합니다.
• 따라서 예시는 다음과 같은 순서를 따릅니다.
  • [to] → [to, be] → [to, be, or] → [to, be, or, not] → [to, be, or, not, to] → "to" 출력
    → [to, be, or, not, be] → "be" 출력 → "not" 출력 → [to, be, or, that] → "that" 출력 → "or" 출력
    → "be" 출력 → [to, is] 

 

Stack : linked-list representation

 

Stack : linked-list impolementation in Java

class LinkedStackOfStrings:
    def __init__(self):
        self.first = None
    
    class Node:
        def __init__(self):
            self.item = None
            self.next = None
    
    def isEmpty(self):
        return self.first == None
    
    def push(self, item):
        oldfirst = self.first
        self.first = self.Node()
        self.first.item = item
        self.first.next = oldfirst
    
    def pop(self):
        item = self.first.item
        self.first = self.first.next
        return item

• 사실 Java로 쓰인 코드를 파이썬으로 변경하면 위와 같지만 파이썬스럽지는 않습니다.
  제가 linked list에 대한 개념이 부족해서 그냥 직역해버렸습니다.
• 파이썬에서는 굳이 이런 걸 쓰지 않아도 되지만, 다른 언어에서는 배열을 한 번 선언하면 길이나 자료형이 고정됩니다.
  그렇기 때문에 어떤 아이템을 추가하거나 제거하는 것이 아주 번거로운 과정인데요,
  이를 해결하기 위해 사용되는 것이 linked list입니다.
  이는 각 아이템을 node라고 부르며, 각 노드는 어떤 값을 지니고 다음 노드에 대한 주소를 가리키고 있습니다.
  그래서 어떤 아이템을 추가하거나 삭제할 때는 가리키고 있는 연결 관계에만 변화를 주면 되는 것이죠.

 

Stack : linked-list implementation performance

• Implementation 코드에서 볼 수 있듯이 어떤 종류의 반복문 등도 포함되지 않기 때문에 상수 시간이 걸립니다.

 

Stack : array implementation

• 이번에는 linked list가 아니라 단순 array로 구현한 것인데, 사실 파이썬에서는 차이가 없는 내용이라서 굳이 코드를 작성하지는 않았습니다.

 

Stack considerations

• Stack 자료형을 사용할 때는 추가로 고려할 사항들이 있습니다.
  • 비어있는 stack에 pop을 실행하는 underflow, 혹은 배열의 사이즈를 변경하는 overflow가 있습니다.
  • 또한 null 아이템을 추가하는 것이 가능한지 아닌지도 결정해야 합니다.
  • 마지막 litering은 pop으로 꺼내서 더이상 존재하지 않는 아이템의 주소를 가리키고 있는 것을 말합니다.
    이것 역시 파이썬에서는 크게 신경쓰지 않고 코딩하는 요소입니다.

 

 

출처: Coursera, Algorithms, Part 1, Princeton University