자료구조는 컴퓨터내의 데이터들을 효율적으로 저장하고 사용하는 방법들이다.

Stack ADT(Abstract Data Type)

여기서 ADT란 자료구조의 실제 구현 방법을 설명하지 않고 간단히 자료 구조가 어떤 features와 operations을 가지고 있는지 나타내는 타입이다.

  • 실생활에서 쉽게 스택하면 떠올릴 수 있는 것들이 책쌓기, 접시쌓기이다. 제일 위에 있는 책이나 접시만 접근 가능하고 제일 윗부분에서만 책을 새로 넣거나 뺄 수 있다.
  • Last-In-First-Out (LIFO)
  • 스택은 Top 이라고 부르는 한쪽 끝에서만 데이터를 삽입, 삭제할 수 있는 제한된 리스트

Operations

(1) Push(x)

- 데이터를 Top에 삽입 

(2) Pop(x)

- Top에 있는 데이터를 뽑기 (삭제)

(3) Top(x)

- Top 에 있는 값 확인 

(4) IsEmpty(x)

- list가 Empty 인지 확인 

=> Stack 은 element의 삽입, 삭제가 시간 복잡도 <mark>Constant Time or O(1) </mark>으로 가능하다.

Applications

  • Function Calls/ Recursion
  • Undo in an editor
  • Balanced Parenthese { ( ) }

Implementaion of Stacks

스택은 Array, Linked list 로 구현할 수 있다. 파이썬에서는 array가 없고 list가 내장 객체로 있기 때문에 List, Linked list로 구현가능하다.

(1) List

class Stack:
    def __init__(self):
        self.container == list()

    def push(self, data):
        self.container.append(data) # append는 list에 데이터 추가하는 메소드 

    def pop(self, data):
        self.container.pop() # python list가 pop 기능 제공

    def is_empty(self): # list가 비었는지 확인 
        if not self:
            return True
        else:
            return False

    def peek(self): # Top 데이터 확인
        return self.container[-1] # 리스트의 마지막 요소의 인덱스는 -1

if __name__ == "__main__":
        s = Stack()
        s.push(1)
        s.push(2)
        s.push(3) 

        while s:
        data = s.pop()
        print(data, end=' ') # 3 2 1 

(2) Linked list

파이썬에서 Linked list는 Node 클래스를 생성하여 구현할 수 있다. (Linked list 는 노드들이 연결된 구조인데 노드에는 데이터와 다음 노드의 주소값이 저장된다, 제일 마지막 노드의 주소값 자리에는 None이 저장된다. )

linked list의 경우 Node를 삽입 할때, 첫 엘리먼트에 Node를 삽입할 때는 시간 복잡도가 O(1) 이지만, 제일 마지막 노드에 새 Node를 삽입하기 위해서는 첫번째 엘리먼트부터 그다음 엘리먼트.... n-1번째 엘리먼트까지 이동한 후 새로 Node를 추가해야하기 때문에 O(N)이 소요된다. 그러므로 Linked list는 제일 앞 노드(TOP)에서 데이터가 추가되고 삭제된다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack: 
    def __init__(self):
        self.head = None 

    def is_empty(self):
        if not self.head:
            return True
        return False

    def push(self, data):
        new_node = Node(data)

        new_node.next = self.head
        self.head = new_node

push 함수

Stack-linkedlist.jpeg

먼저 새 노드의 next를 현재 head로 대입 후 같은 값을 가리키게 하고, self.head = new_node 로 지정하여 새로운 Node로 head 값 변경

    def pop(self):
        if self.is_empty():
            return None

        ret_data = self.head.data
        self.head = self.head.next
        return ret_data 

Stack-linkedlist-pop.jpeg

head가 가리키고 있는 값의 data를 ret_data 에 저장 후, head 를 head가 가리키고 있는 노드의 next 를 대입하여 head를 변경

head는 Node 인가 ? 아니면 첫번째 element의 주소값을 저장해놓은 곳인가 ?
self.head.next : Node가 아닌데 .next를 사용할 수 있나 ? 아니면 head가 첫 엘리먼트를 가리키고 있기 때문에 첫엘리먼트의 next까지 접근이 가능한 건가 ??


    def peek(self,data):
        if self.is_empty():
            return None

        return self.head.data

    if __name__ == '__main__':
        s = Stack()

        print(s.is_empty())

        s.push(1)
        s.push(2)
        s.push(3)

        print("peek of data : {}".format(s.peek)))

        while not s.is_empty():
            print(s.pop()) # 3 2 1