[CLRS] [10-2] Stack(스택)

1. Intro

- 스택은 후입선출(LIFO, Last In First Out) 구조의 선형 자료구조이다.

- 데이터를 한 쪽 끝에서만 추가하거나 삭제할 수 있는 특징을 가지며, 보통 접시를 쌓아 올리는 것과 유사한 방식

- 즉, 스택에서 가장 나중에 삽입된 요소가 가장 먼저 제거된다.

 

2. 스택의 주요 특징

- 후입선출(LIFO) : 

-- 가장 마지막에 들어온 데이터가 가장 먼저 나간다.

-- 스택의 구조적 특성 때문에 데이터를 삽입하거나 삭제할 수 있는 위치는 Top으로 고정된다.

 

- 한 방향에서만 접근 가능:

-- 스택은 끝부분에서만 데이터를 접근할 수 있기 때문에 중간에 삽입이나 삭제를 할 수 없다.

 

3. 스택의 메소드

3.1. push()

- 스택의 끝, 즉 Top 위치에 데이터를 추가하는 연산이다. 

- 데이터를 쌓는다고 생각하면 편하다.

- O(1)

 

3.2. pop()

- 스택의 Top위치에 있는 데이터를 삭제하고 반환하는 연산이다.

- 가장 최근에 추가된 데이터가 제거된다.

- O(1)

3.3. peek:

- 스택의 Top에 있는 데이터 값을 확인하지만, 스택에서 제거하지 않는 연산이다.

- O(1)

3.4. is_empty:

- 스택이 비어 있는지 여부를 확인하여, 스택에 데이터가 없으면 True을 반환한다.

- O(1)

3.5. size:

- 현재 스택에 포함된 데이터 개수를 반환함

 

4. 스택 구현

4.1. 파이썬 내장 배열 기반 스택 구현

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, item):
        self.stack.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("Pop from an empty stack")
    
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("Peek from an empty stack")
    
    def is_empty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

# 스택 사용 예시
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print("Top item:", s.peek())  # 3
print("Pop item:", s.pop())   # 3
print("Is stack empty?", s.is_empty())  # False
print("Stack size:", s.size())  # 2

4.2. 연결 리스트 기반 스택 구현

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

class LinkedListStack:
    def __init__(self):
        self.top = None
        self._size = 0

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from an empty stack")
        popped_value = self.top.value
        self.top = self.top.next
        self._size -= 1
        return popped_value

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from an empty stack")
        return self.top.value

    def is_empty(self):
        return self.top is None

    def size(self):
        return self._size

# 연결 리스트 스택 사용 예시
s = LinkedListStack()
s.push(1)
s.push(2)
s.push(3)
print("Top item:", s.peek())  # 3
print("Pop item:", s.pop())   # 3
print("Is stack empty?", s.is_empty())  # False
print("Stack size:", s.size())  # 2