스택(Stack)의 개념과 특징

Stack의 정의

스택은 쌓다, 누적하다라는 의미를 가지고 있습니다. 마치 접시를 쌓아 놓는 것 처럼 데이터를 순서대로 쌓는 자료 구조 입니다.

Stack의 구조

• 입력과 출력이 하나의 방향, 즉 스택의 최상단에서만 이루어지며, 이를 제한적 접근이라고 합니다.
• 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 라고 부르기도 합니ㅏㄷ.
• Stack에 데이터를 넣는 것을 PUSH, 데이터를 꺼내는 것을 POP이라고 합니다.

Stack의 특징

1. LIFO(Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조입니다. 위에 말한 것 처럼 입력과 출력이 한 방향이기 때문에 실린더안에 구슬을 하나씩 쌓아 넣는 것 처럼 제일 아래것을 꺼내기 위해서는 제일 위부터 차례대로 출력해야 합니다.

예) 데이터 1, 2, 3, 4, 5를 스택에 차례로 넣습니다. stack.push(데이터) | 5 | <- top | 4 | | 3 | | 2 | | 1 | 데이터 1이 제일 먼저 입력되고 데이터 5가 마지막으로 입력됩니다.

예) 스택을 전부 비우려고 합니다. stack.pop() | | | | | | | | | | 5, 4, 3, 2, 1 가장 마지막에 있는 데이터 5부터 차례대로 나오게 됩니다.

이런 특성으로 스택 구조 내에서 특정 데이터를 조회할 수 없으며, 스택의 최상단에서 데이터를 저장하고 꺼낼 수 있는 특징이 있습니다.

2. 하나의 입출력 방향을 가지고 있습니다.

스택 자료구조는 데이터를 넣고 뺄 수 있는 곳이 스택의 가장 최상단으로 오직 한 군데 입니다. 즉 데이터를 입력할 때 데이터는 스택의 가장 최상단에 입력되고, 출력할 때도 스택의 가장 최상단부터 출력됩니다.

3. 데이터는 하나씩 넣고 뺄 수 있습니다.

입구가 하나이기 때문에 한 개씩 여러번 넣어서 스택 내부에 데이터가 쌓여 있다고 해도 데이터를 뺄 때는 스택의 가장 최상단에서 한 번에 한 개의 데이터만 뺄 수 있습니다.

Stack 자료 구조의 장점

스택에 저장된 데이터를 가져오는 속도가 매우 빠릅니다.

스택은 후입선출 구조이기 때문에, 삽입과 삭제가 최상단에서만 이루어집니다. 따라서 스택에서 데이터를 삽입하거나 삭제할 때, 다른 데이터의 위치를 변경할 필요가 없습니다. 데이터를 저장할 때나 검색할 때 항상 스택의 최상단에서만 행위가 이루어져서 데이터를 저장하고 검색하는 프로세스가 매우 빠릅니다.

그렇기 때문에 스택의 크기와 상관없이 항상 매우 빠르게 처리됩니다. 데이터를 삽입, 삭제하는데 모든 데이터를 순회할 필요가 없기 때문입니다.

Stack 자료 구조의 단점

스택은 중간 요소의 접근이 제한됩니다.

스택은 최상단 요소에만 직접적인 접근이 가능하며, 중간에 있는 요소에는 직접적인 접근이 불가능합니다. 중간에 있는 요소에 접근하기 위해서는 해당 요소 위에 있는 요소들을 모두 pop()하여 접근해야합니다.

데이터의 최대 개수를 미리 정해야합니다.

스택은 크기를 고정해서 사용하는 자료 구조 입니다. 만약 스택의 크기를 초과하여 데이터를 저장하려고 하면 스택오버플로우(Stack Overflow)가 발생할 수 있습니다.

그래서 스택을 동적할당 방식으로 구현하기도 합니다. 동적할당은 초기에 메모리 공간을 정해두지 않고, 필요할 때마다 할당하는 방식으로 데이터 삽입,삭제하는 경우 0(1)에 가능하며, 최대 메모리공간 내에서 리스트 크기 제한이 없다는 특징이 있습니다.

Stack의 활용

대표적인 예시로 웹 브라우저의 뒤로 가기와 앞으로 가기 기능이 스택을 사용합니다.

여기 두 스택이 있습니다. 하나는 방문한 페이지 이력을 저장하는 뒤로 가기 스택, 다른 하나는 뒤로가기를 한 후에 앞으로 가기를 할 수 있도록 정보를 저장하는 앞으로 가기 스택입니다.

그리고 아래의 순서를 따릅니다.

1. 사용자가 웹페이지를 방문할 때마다, 현재 페이지를 뒤로 가기 스택에 보관합니다.
2. 사용자가 뒤로 가기 버튼을 클릭하면, 현재 페이지를 앞으로 가기 스택에 push하고 앞으로 가기 스택의 가장 마지막으로 보관된 페이지를 pop하여 현재 페이지로 설정합니다.
3. 사용자가 앞으로 가기 버튼을 클릭하면, 현재 페이지를 뒤로 가기 스택에 push하고 앞으로 가기 스택의 가장 마지막으로 보관된 페이지를 pop하여 현재 페이지로 설정합니다.

이 외에도 컴퓨터 내부의 프로세스 구조, 프로그래밍 언어의 메모리 관리, 문자열 역순 출력 등에 스택이 사용됩니다.

스택(Stack)의 기본 동작

스택은 선형 자료구조이며 일렬로 나열된 요소들의 집합입니다.

이 요소들은 스택의 최상단을 기준으로 쌓이며, 스택의 맨 아래에 위치한 요소는 스택의 바닥(bottom)이라고 합니다.

Push()

• push()는 스택에 새로운 요소릉 추가하는 작업입니다.
• 새로운 요소는 스택의 최상단에 삽입됩니다.
• 스택이 비어있을 경우, 첫 번째 요소가 바닥이자 최상단이 됩니다.

def push(stack, item):
    stack.append(item)
----------------------------------
# 예
stack = []
push(stack, "apple")
push(stack, "banana")
push(stack, "cherry")
print(stack)
#출력: ["apple", "banana", "cherry"]

POP()

• pop()은 상단에 위치한 요소를 제거하고 반환하는 작업입니다.
• 가장 최근에 추가된 요소가 가장 먼저 제거됩니다.
• pop()을 수행하면 상단 요소는 제거되며, 그 아래에 위치한 요소가 새로운 상단이 됩니다.

def pop(stack):
    if not stack:
        return "Stack is empty."
    else:
        return stack.pop()
-------------------------------------------
stack = ["apple", "banana", "cherry"]
print(pop(stack))  # 'cherry'
print(stack)  # ['apple', 'banana']

peek()

• peek()은 상단에 위치한 요소를 반환하는 작업입니다.
• peek()을 통해 상단에 위치한 요소를 확인할 수 있습니다.
• peek()을 수행하더라도 요소가 제거되지 않습니다.

def peek(stack):
    if not stack:
        return "Stack is empty."
    else:
        return stack[-1]
----------------------------------------
stack = ["apple", "banana", "cherry"]
print(peek(stack))  # 'cherry'

isEmpty

• isEmpty는 스택이 비어있는지 확인하는 작업입니다.
• 스택이 비어있는 경우 true를 반환하고, 비어있지 않을 경우 false를 반환합니다.

def isEmpty(stack):
    if not stack:
        return True
    else:
        return False
------------------------------------
stack = ["apple", "banana", "cherry"]
print(isEmpty(stack))  # False

스택의 시간 복잡도와 공간 복잡도

스택의 시간복잡도(Time Complexity)

스택은 그 특성상 데이터를 추가하거나 제거하는 데 있어서 상수 시간, 즉 0(1)의 시간 복잡도를 가집니다. 이는 상단에 위치한 요소에만 접근하고 조작하기 때문입니다. 따라서 스택의 크기와 무관하게, 스택의 주요 동작들은 모두 상수 시간에 수행됩니다.

스택의 공간복잡도

스택의 공간복잡도는 구현하는 방식에 따라 다릅니다.

• 배열(Array) 기반 구현: 미리 정의된 크기 배열을 사용하여 구현합니다. 스택의 크기가 고정되어 있으므로, 배열의 크기 n만큼의 공간이 필요합니다. 배열 기반 스택의 공간복잡도는 O(n)입니다.
• 연결 리스트(Linked List) 기반 구현: 연결 리스트 기반 스택은 동적으로도 크기가 조정되는 연결 리스트를 사용하여 구현됩니다. 각 요소는 노드로 표현되고, 노드에는 데이터와 다음 노늗를 가리키는 링크가 포함됩니다. 연결 리스트 기반 스택의 공간 복잡도는 O(n)입니다. 여기서 n은 스택에 저장된 요소의 개수입니다.
• 동적 배열(Dynamic Array) 기반 구현: 동적 배열 기반 스택은 동적으로 크기가 조정되는 배열을 사용하여 구현됩니다. 요소를 추가하거나 제거할 때 배열의 크기를 동적으로 조정할 수 있습니다. 동적 배열 기반 스택의 공간복잡도는 O(n)입니다. 동적 배열의 크기가 변경될 때마다 일시적으로 추가적인 메모리 할당 및 해제가 발생할 수 있습니다.
• 프로그래밍 언어별 내장 스택: 특정 프로그래밍 언어에서 스택을 내장(built-in)자료 구조로 제공합니다. 이 경우 그 공간 복잡도는 해당 언어의 스택 구현에 따라 다를 수 있습니다.
  • 예를들어, C++의 ` std::stack`은 동적 배열을 기반으로 하므로, 요소를 저장하기 위한 메모리 고간을 동적으로 할당하고 해제하는 과정에서 추가적인 메모리 사용이 발생할 수 있습니다. Java의 java.util.Stack 과 Python의 리스트를 활용한 스택도 마찬가지 입니다. 이들은 모두 동적 배열로 구현되어 있어, 크기가 동적으로 조정됩니다. 한편, C는 스택을 내장 자료구조로 제공하지 않으므로, 직접 구현해야 합니다.