자료구조 - 스택(Stack)

1. 스택(Stack)이란?

스택(Stack)은 한쪽 방향으로만 데이터의 삽입과 삭제가 이루어지는 선형 자료구조이다.
후입선출(LIFO, Last In- First-Out)은 한쪽 방향으로만 데이터의 삽입과 삭제가 이루어지는 선형 자료구조이다.

---

2. 스택의 동작 방식

스택은 맨 위(Top)에서만 데이터의 삽입과 삭제가 이루어진다.

---

1️⃣ 삽입하는 작업 (Push)

위의 예시처럼 10 → 20 → 30 순서로 데이터를 넣으면, 가장 마지막에 들어온 30이 맨 위(Top)에 위치하게 된다.

---

2️⃣ 삭제하는 작업 (Pop)

반대로 데이터를 제거하는 pop() 작업은 맨 위 데이터부터 제거된다. 따라서 pop()을 실행하면 가장 마지막에 들어온 30부터 먼저 삭제되며, 이후 20, 10 순서대로 제거된다.

---

3. 스택의 장,단점

3.1 장점

1️⃣ 빠른 처리 속도

스택(Stack)은 데이터를 넣고 뺄 때 항상 맨 위(Top) 에서만 작업이 이루어진다.

배열처럼 중간에 데이터를 추가하거나 삭제하기 위해 나머지 데이터를 밀거나 당길 필요가 없기 때문에, push()와 pop() 동작이 비교적 빠른 편이다.

2️⃣ 비교적 구현이 단순하다

스택의 규칙은 "맨 위에 넣고 뺀다" 뿐으로 구조가 매우 단순한 편이다.

 

실제로 배열(Array)이나 연결 리스트(Linked List)를 활용해 비교적 쉽게 구현할 수 있으며, 동작 방식도 직관적이라 자료구조 입문 단계에서 이해하기 쉬운 편이다.

---

3.2 단점

1️⃣ 특정 데이터 접근이 어렵다

스택은 배열처럼 인덱스를 이용해 원하는 데이터에 접근하는 랜덤 접근이 불가능하다.

 

오직 맨 위에 있는 데이터만 확인할 수 있기 때문에, 중간이나 가장 아래에 있는 데이터를 확인하려면 위에 쌓여 있는 데이터를 하나씩 꺼내야(pop) 한다.

---

2️⃣ 오버플로우 & 언더플로우 발생 가능성

스택을 크기가 고정된 배열 기반으로 구현했을 경우 주의해야 할 점이 있다.
정해진 크기를 초과해서 데이터를 계속 삽입하려고 하면, 저장 공간을 넘어서게 되면서 스택 오버플로우(Stack Overflow) 가 발생할 수 있다.
반대로 이미 비어 있는 스택에서 계속 데이터를 꺼내려고 하면 스택 언더플로우(Stack Underflow) 가 발생하게 된다.

오버플로우는 스택이 가득 찬 상태에서 데이터를 더 넣으려는 경우, 언더플로우는 비어 있는 스택에서 데이터를 꺼내려는 경우라고 이해하면 된다.

---

4. 실제 활용 사례

4.1 웹 브라우저 방문 기록

웹 브라우저는 사용자가 방문한 웹 페이지 기록을 저장하고 관리할 때 스택 구조를 활용한다.
새로운 페이지에 접속할 때마다 해당 웹 페이지의 주소가 스택에 쌓이고(Push), 뒤로 가기버튼을 누르면 가장 마지막에 저장된 페이지부터 순서대로 꺼내어(Pop)화면에 보여주는 방식으로 동작한다.

---

4.2 운영체제의 메모리 할당

프로그램이 실행될 때 함수 호출 과정에서 스택 구조가 사용된다.
예를 들어 함수가 호출되면 해당 함수의 지역 변수나 실행 정보가 스택에 저장된다.
이후 함수 실행이 끝나면 가장 마지막에 저장된 정보부터 제거되며 이전 실행 흐름으로 돌아가게 된다.

---

5.  구현

class Stack:

# 생성자
  def __init__(self):
    self.items=[]

  # ✅ push() :새로운 데이터 추가하는 메서드

  def push(self,data):
    self.items.append(data)

 # ✅ pop() : 가장 마지막 데이터를 반환 후 스택에서 제거하는 메서드
  def pop(self):

    if len(self.items) > 0 : # 스택에 요소가 있을 때
      popped=self.items.pop() 
      return popped # pop한 데이터를 return

    else: # 스택이 비어있을 때
      print("비어 있는 스택입니다")

# ✅ display() : 현재 Stack안의 요소들을 보여준다 
  def display(self):
    print("==== 현재 Stack 상태 ====")

    if len(self.items)==0: # 스택이 비어있으면 
      print('비어 있음') # '비어 있음' 메세지를 출력

    else:     # 스택에 요소가 있을 때
      for item in self.items:
        print(item,end=" ")

      print()

      print("=========================")

stack=Stack()

stack.push(10)
stack.push(20)
stack.push(30)

stack.display()

print('pop() 실행: ',stack.pop())
stack.display()

 

실행결과

---

6. 스택(Stack)은 왜 후입선출(LIFO)구조를 사용하는가?

스택은 데이터를 한쪽 방향(Top) 에서만 넣고 뺄 수 있는 구조이다.
가장 위에 새 데이터가 쌓이고 삭제 역시 가장 위에서만 이루어지기 때문에 가장 나중에 들어간 데이터가 가장 먼저 나오게 된다.
그래서 스택은 자연스럽게 후입선출(LIFO, Last In First Out) 구조를 사용한다.

---

7.  웹 브라우저의 뒤로가기 기능은 어떤 자료구조를 사용할까?

스택을 사용한다.

사용자가 새로운 페이지에 접속할 때마다 해당 페이지 정보가 차례대로 스택에 저장된다(push).
이후 뒤로 가기 버튼을 누르면 가장 마지막에 방문했던 페이지부터 꺼내어(pop) 이전 페이지로 이동하게 된다.
따라서 웹 브라우저의 뒤로가기 기능은 가장 최근 기록부터 처리되는 방식이기 때문에 스택의 후입선출(LIFO) 구조와 잘 맞는다.