Data Structure - Stack

Data Structure - Stack

Stack

스택은 가장 대표적인 자료구조 중 하나이므로 잘 알아두자!!!

책상에 보면 책이 쌓여 있는 것을 볼 수 있다.
맨밑에 있는 책을 꺼내려면, 위에서 부터 하나씩 치우고 꺼내야 한다.

스택은 책이 쌓이고 치워지는 과정과 같다.
처음 들어온 데이터가 마지막에 나가고, 마지막에 들어온 데이터가 먼저 나간다.
스택은 LIFO(Last-In,First-Out) 형태를 가진다.

스택은 대표적으로 내부프로세스의 함수 동작 방식에 활용된다.

스택의 주요 기능 push(), pop()

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

스택은 구조가 단순하며, 구현이 쉬우며, 데이터 처리 속도가 빠르다.
하지만 미리 데이터의 최대 개수를 정해두어야 한다는 단점이 있다.

스택구조와 프로세스스택

스택구조는 프로세스 실행 구조의 가장 기본이다.
재귀함수로 알아보자.

#재귀함수
def recursive(data):
    if data < 0:
        print("end")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)

recursive(5)

# 데이터는 5부터 들어간다. 
# 들어가다가 다시 재귀함수를 마나서 4,3,2,1,0 순으로 들어간다.
# -1이 되면 "end"를 출력하고, 그동안의 쌓인 프린트 문을 실행한다.
# 스택과 같이 먼저 들어간 데이터가 맨 마지막에 나온다.

5
4
3
2
1
0
end
returned 0
returned 1
returned 2
returned 3
returned 4
returned 5

push와 pop을 구현해보자

push는 스택에 데이터를 넣는 것이다.
pop는 스택에서 데이터를 꺼내는 것이다.
스택은 LIFO로 구현해야 한다.

방법1

class MyStack:
    def __init__(self):
        self.stack_list = []
    
    def push(self,data):
        self.stack_list.append(data)
    
    def pop(self):
        if len(self.stack_list) > 0:
            self.stack_list.pop()


stack = MyStack()
stack.push(10)
stack.pop()

방법2

stack_list = []

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

def pop():
    data = stack_list[-1]
    del stack_list[-1] # 마지막 데이터를 꺼낸다.
    return data # 사라질 데이터를 리턴값으로 준다.


push(10)
print(stack_list)
print(pop())
print(stack_list)

참고

https://www.fun-coding.org/daveblog.html