CS 공부 - [스택]

1️⃣ 스택이란?

스택(Stack)이라는 것은 쌓아올린다는 의미입니다.

자료구조에서 스택은 자료들을 한층한층 쌓아 올린다는 것을 의미합니다.

위의 그림이 크기 5인 스택을 묘사한 그림입니다.

스택에는 두가지 연산방법이 존재합니다.

1. PUSH

   스택의 PUSH 연산은 스택에 원하는 자료를 넣고자할 때 수행하는 연산입니다.

   스택에 PUSH를 하게되면 넣은 원소는 스택의 공간에 들어갈 수 있는 가장 아래쪽에 원소를 위치시킵니다.

   쉽게 말하면 데이터 탑을 쌓는 연산입니다.

2. POP

   스택의 POP 연산은 스택의 맨위의 원소를 빼고자할 때 수행하는 연산입니다.

   데이터 탑의 맨 윗 부분을 제거한다고 보시면 될 것 같습니다.

이러한 스택구조를 LIFO(Last In First Out)구조 라고도 합니다.

2️⃣ 스택의 구현

스택은 보통 배열로 구현을 합니다.

왜냐하면 스택의 pop연산은 맨 마지막 부분을 삭제하는 것이기 때문에 시간복잡도상 배열로 구현했을 때 단점이 없기 때문입니다.

하지만 메모리상으로는 삭제된 원소를 반환을 안해주기 때문에 안좋은 점은 있겠지만 알고리즘 문제를 풀 땐 메모리는 거의 고려를 안하므로 보통 배열로 구현합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
STACK_SIZE = 5
stack = []
top = -1

def push(item): # append 메소드로 대체가능
    if top>=STACK_SIZE-1:
        print("스택이 가득찼습니다.")
        return
    else:
        top+=1
        stack[top]=item

def pop(): # pop메소드로 대체 가능
    if top==-1:
        print("스택이 비어있습니다")
        return 0
    else:
        return stack[top--]

# 스택의 맨 꼭대기를 출력할때: 보통 peek이라고 부릅니다.
print(stack[-1])

보통 스택은 append, pop 메소드를 쓰면 되는데 위에서는 한번 로직을 따라가면 좋을 것 같아 임의로 구현을 해봤습니다.

3️⃣ 스택의 시간복잡도

4️⃣ 스택이 활용되는 곳

1. 브라우저 히스토리 : 브라우저의 기록을 스택으로 쌓고 뒤로가기를 누를때마다 스택을 pop하는 형식을 사용합니다.

2. 괄호검사, 후위표기식 : 스택으로 괄호가 잘열리고 닫혔는지를 검사하며, 스택으로 후위표기식을 계산합니다.

3. 역순 문자열만들기 : 역순 문자열을 만들때 차례로 쌓인 문자열을 하나하나 가져오면 쉽게 역순 문자열을 만들 수 있습니다.

4. 프로그램 호출 스택 : 보통 재귀적인 구조를 호출할 때 스택이 사용되곤 합니다.

여기서 대표로 가장 많이 면접에 출제된다고 하는 호출 스택을 그림으로 표현해보고 이해해보도록 하겠습니다.

1번부터 차근차근 따라가 보도록하겠습니다.

1. 프로그램 실행을 시작하면 main함수가 호출되어 실행되면서 main함수에 대한 정보를 시스템 스택에 저장합니다.

   

2. 메인 함수를 실행하던 중에 function1함수를 만나면 함수 호출과 복귀 등 작업 전환을 위해 필요한 정보를 스택 프레임에 저장하고 시스템 스택에 삽입합니다. 스택 프레임에 main함수로 복귀할 주소가 저장됩니다.

   

3. 호출된 function1함수를 실행합니다.

4. function1 함수를 실행하던중에 function2함수를 만나면 함수 호출과 복귀 등 작업 전환을 위해 필요한 정보를 스택 프레임에 저장하고 시스템 스택에 삽입합니다. 스택 프레임에 function1함수로 복귀할 주소가 저장됩니다.

   

5. 호출된 function2함수를 실행합니다.
6. function2 함수 실행이 끝나면 시스템 스택에 쌓였던 정보들을 이용해 function1함수로 돌아갑니다. 이 때 해당 시스템 스택은 pop 됩니다.
7. function1 함수로 복귀해 function1 함수의 나머지 부분을 실행합니다.
8. function1 함수실행이 끝나면 시스템 쓰택에 쌓였던 정보들을 이용해 main함수로 돌아갑니다. 이 때 function1 시스템 스택은 pop됩니다.
9. main함수로 복귀해 main함수를 끝내고 마지막으로 남아있던 main함수 시스템 스택도 pop한 후에 프로그램이 종료됩니다.

5️⃣ 마치며

오늘은 스택에 대해 알아보았습니다.

함수 스택은 면접에도 자주 나오는 문제라고 하니 꼭 알아 두어야 할 것 같습니다.

더 자세히 시스템 호출 스택에 대해서는 운영체제쪽 공부를 복습할 때 한번 포스팅 해보도록 하겠습니다.

읽어주셔서 감사합니다.

• Previous
  CS 공부 - 네트워크 [SOP와 CORS]
• Next
  CS 공부 - [큐]