C/C++/자료구조

내가 정리하는 자료구조 01 Stack

Stack

꼭 알아둬야 할 자료 구조: 스택 (Stack)

  • 데이터를 제한적으로 접근할 수 있는 구조
    • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

  • 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

    • 큐: FIFO 정책 -> 줄 세우기
    • 스택: LIFO 정책 -> 책 쌓기

    1. 스택 구조

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

      • LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
      • FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
      • 참고로 Queue는 FIFO라고 많이 얘기하지만, Stack은 그냥 Stack이라고 한다.

    • 대표적인 스택의 활용

      • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

    • 주요 기능

      • push(): 데이터를 스택에 넣기
      • pop(): 데이터를 스택에서 꺼내기

    • Visualgo 사이트에서 시연해보며 이해하기 (push/pop 만 클릭해보며): https://visualgo.net/en/list


    그림으로 이해해보기

2. 스택 구조와 프로세스 스택

  • 스택 구조는 프로세스 실행 구조의 가장 기본
    • 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해 필요
    • stack이랑 queue는 일시적으로 자료를 보관할때 사용!!!

재귀 함수

1
2
3
4
5
6
7
def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)
실행
1
recursive(4)
결과
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3
returned 4
  • Process에서 함수가 어떻게 동작하는지 그리고 그것이 어떻게 Stack이라는 자료구조와 연결이 되는지 중점적으로 설명하면 다음과 같다. Program이 실행되는 상태를 Process라고 하는데 그 Process안에서 함수가 호출이 된 것이므로 Process Stack에 아래 그림과 같이 쌓이게 된다. recursive 함수가 최종적으로 끝나게 되면, Stack 구조와 같이 제일 마직막 실행된 함수부터 실행을 마치게 되어 위와 같은 결과가 출력이 되는 것이다.

Stack Process

3. 자료 구조 스택의 장단점

  • 장점
    • 구조가 단순해서, 구현이 쉽다.
    • 데이터 저장/읽기 속도가 빠르다.
  • 단점 (일반적인 스택 구현시)
    • 데이터 최대 갯수를 미리 정해야 한다.
      • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
    • 저장 공간의 낭비가 발생할 수 있음
      • 미리 최대 갯수만큼 저장 공간을 확보해야 함

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

4. 파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기

  • append(push), pop 메서드 제공
1
2
3
4
data_stack = list()

data_stack.append(1)
data_stack.append(2)
1
data_stack
결과
1
[1, 2]
1
data_stack.pop()
결과
1
2

5. 프로그래밍 연습

연습1: 리스트 변수로 스택을 다루는 pop, push 기능 구현해보기 (pop, push 함수 사용하지 않고 직접 구현해보기)
1
2
3
4
5
6
7
8
9
stack_list = list()

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

def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data
1
2
for index in range(10):
    push(index)
1
pop()
결과
1
9

또 다른 방식으로 구현하는 Stack 구조

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 많은 언어들이 실제 구현되어 있는 것을 보면 실제 자료는 container라는 stack안의 공간에 있고, stack은 인터페이스만 제공
class Stack:
    def __init__(self):
        # 실제 데이터를 가지고 있는 자료구조
        self.container=list() # 빈 list 객체가 만들어져서 container에 저장.

    def empty(self):
        if not self.container: # 비어있으면 true가되니까
            return True
        return False

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

    def pop(self):
        return self.container.pop()

    def peek(self):
        return self.container[-1]
1
2
3
4
5
6
7
8
9
10
s=Stack()

s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.push(5)

while not s.empty():
    print(s.pop(), end='  ')
결과
1
5  4  3  2  1

Node를 활용한 Stack 구조 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Node:
    def __init__(self, data=None):
        self.__data=data
        self.__next=None

    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, data):
        self.__data=data

    @property
    def next(self):
        return self.__next

    @next.setter
    def next(self, n):
        self.__next=n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class LStack:
    def __init__(self):
        #인스턴스 멤버
        self.top=None

    def empty(self):
        if self.top is None:
            return True
        return False

    def push(self, data):
        new_node = Node(data)
#         new_node.__data=data
#         if self.empty():
#             self.top = new_node
#             return

        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.empty():
            return None
        cur = self.top
        self.top = self.top.next
        return cur.data


    def peek(self):
        if self.empty():
            return None
        cur = self.top
        return cur.data
1
2
3
4
5
6
7
8
9
10
s = LStack()

s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.push(5)

while not s.empty():
    print(s.pop(), end="  ")
결과
1
5  4  3  2  1
1
2
3
4
5
s = LStack()

s.push(1)
s.push(2)
s.empty()
결과
1
False
Share