[자료구조] 스택(Stack)이란?

Posted on | In
스택의 개념과 구조. 스택의 장단점. 스택의 메소드와 리스트로의 구현

스택(Stack)이란?

  • 데이터를 제한적으로 접근할 수 있는 구조이다.
    • 한 쪽 끝에서만 자료를 넣거나 뺄 수 있다.
  • 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조이다.(LIFO)

구조

  • 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따른다.

대표적 스택의 활용

  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식에서 사용된다.

기능

  • push(): 데이터를 스택에 넣는다.
  • pop(): 데이터를 스택에서 꺼낸다.

프로세스 스택

  • 스택 구조는 프로세스 실행 구조의 가장 기본이 된다.
    • 함수 호출 시 프로세스 실행 구조를 스택과 비교해서 이해할 필요가 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 재귀 함수
def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)


recursive(4)
'''
4
3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3
returned 4
'''

image

장단점

장점

  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장 및 읽기의 속도가 빠르다.

단점

  • 데이터 최대 갯수를 미리 정해야한다.
    • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능하다.
  • 저장 공간의 낭비가 발생할 수 있다.
    • 미리 최대 갯수만큼 저장 공간을 확보해야한다.

스택은 단순하고 빠른 성능을 위해 사용되므로 보통 배열 구조를 활용하여 구현하는 것이 일반적이다. 이 경우, 위에서 열거한 단점이 있을 수 있다.

메소드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
data_stack = list()

data_stack.append(1)
data_stack.append(2)


data_stack
'''
[1, 2]
'''


data_stack.pop()
'''
2
'''

리스트로 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
stack_list = list()

def push(data):
    stack_list.append(data)

def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data


for index in range(10):
    push(index)


pop()
'''
9
'''
0%