[자료구조]스택

스택

정의: 한 쪽 끝에서만 데이터(item)을 삭제하거나 새로운 항목을 저장하는 자료구조.

동작: 먼저 들어간 데이터가 먼저 나가는 형식, 선입후출 구조

동작 방법

숫자 6, 7, 3, 5를 순서대로 스택에 입력하면 아래와 같은 그림으로 들어간다.

스택의 입력

먼저 들어간 6이 제일 안쪽에 존재하고, 7-3-5가 이어서 스택에 저장되어 있는 것을 확인할 수 있다.

 

이제 스택을 비우기 위해 스택에 저장된 항목들을 모두 삭제해보자.

스택의 출력

스택의 맨 앞에 저장된 5가 가장 먼저 출력되고, 3-7-6이 이어서 삭제되는 것을 확인할 수 있다.

 

이처럼 스택은 먼저 들어간 항목일수록 나중에 삭제된다는 것을 알 수 있다.

스택의 연산

삽입 연산: 스택에 새로운 항목을 입력하는 연산이다. push라고 한다. 파이썬의 경우 append()를 사용해서 리스트에 추가한다.

 

삭제 연산: 스택에 존재하는 항목을 출력하는 연산이다. pop이라고 한다. 파이썬의 경우 pop()을 사용해서 리스트에서 삭제한다.

실습

스택의 동작을 직접 파이썬 코드로 실습해보자.

아래 순서대로 코드를 진행할 때 스택에 존재하는 항목과 출력된 값을 예측해보고 코드로 확인해보자.

 

1. 숫자 3, 5, 10, 11을 순서대로 스택에 입력하자.

2. 스택의 삭제 연산을 2번 수행하자.

3. 숫자 20, 1을 스택에 입력하자.

 

예상)

1번 항목을 실행하면 스택에는 3이 스택의 제일 안쪽에 존재하고 5-10-11이 이어서 스택에 존재할 것이다.

2번 항목을 실행하면 11과 10이 순서대로 삭제될 것이다. 스택에는 3, 5가 존재할 것이다.

3번 항목을 실행하면 스택에는 3이 스택의 제일 안쪽에 존재하고 5-20-1이 이어서 스택에 존재할 것이다.

 

코드)

## 스택 리스트 선언
stack = []

스택은 파이썬 리스트를 사용하므로 리스트를 선언했다.

## 1. 숫자 3, 5, 10, 11을 순서대로 스택에 입력하자.
stack.append(3)
stack.append(5)
stack.append(10)
stack.append(11)

print(stack[::-1]) ## 최상단 원소부터 출력
print(stack)       ## 최하단 원소부터 출력

## 최상단 스택 출력값
[11, 10, 5, 3]
## 최하단 스택 출력값
[3, 5, 10, 11]

최상단 원소부터 출력하게 되면 스택의 위에 있는 원소부터 출력된다. 반대로 최하단 원소부터 출력하게 되면 스택의 맨 아래있는 원소부터 출력된다.

출력된 값을 보면 예측한 결과와 일치하다.

## 2. 스택의 출력 연산을 2번 수행하자.
print(stack.pop())
print(stack.pop())

print(stack[::-1]) ## 최상단 원소부터 출력
print(stack)       ## 최하단 원소부터 출력

## 처음 삭제 연산 출력
11
## 두 번째 삭제 연산 출력
10
## 최상단 스택 출력
[5, 3]
## 최하단 스택 출력
[3, 5]

삭제 연산을 처음 수행했을 때 11이 출력되고, 두 번째 수행했을 때 10이 출력되었다. 스택에는 3, 5가 저장되어 있다.

예측한 결과와 일치하다.

## 3. 숫자 20, 1을 스택에 입력하자.
stack.append(20)
stack.append(1)

print(stack[::-1]) ## 최상단 원소부터 출력
print(stack)       ## 최하단 원소부터 출력

## 최상단 스택 출력
[1, 20, 5, 3]
## 최하단 스택 출력
[3, 5, 20, 1]

스택에 존재하는 값을 보면 예측한 결과와 일치하다.

정리

1. 스택은 선입후출 동작을 하는 자료구조이다.

2. 스택의 동작은 push, pop이 있다.