[알고리즘(4)] Python으로 알아보는 스택(Stack)

출처: flacticon

 

 

[알고리즘 포스팅 순서]

1. 시간복잡도

2. 배열

3. 연결리스트

4. 스택

5. 큐

6. 트리

7. 그래프

8. 해쉬테이블

9. 정렬(선택, 버블, 삽입, 퀵, 힙, 병합)

10. 코테 대비 백준 문제 풀이 꿀팁

 

 

오늘 알아볼 자료구조는 스택(Stack)이다.

[스택이란?]

스택은 컴퓨터에서 아주 많이 사용되는 자료구조이다.

컴퓨터 메모리의 스택 영역은 함수의 호출과 관계되는 지역변수, 매개변수, 리턴 값등의 임시데이터를 저장한다.

 

스택이란 단어는 ‘차곡 차곡 쌓여진 더미’를 의미한다.

예를 들면 웹 페이지에서 '뒤로 가기' 버튼을 누르면 가장 최근에 보았던 페이지가 다시 나타나는 것과 같다.

 

이를 LIFO(Last-In First-Out, 후입선출) 구조라고 한다.

가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미이다.

 

[구조와 사용]

1. 기본 구조

보통 이해를 돕기 위해 이런 구조로 그린다.

방이 생긴 프링글스 통처럼 생겼다고 생각하면 된다.

 

 

2. push와 pop

push push babe 달콤한 말로~

push는 데이터를 밀어 넣는다.

어떻게? 마치 옷을 개듯이 차곡차곡 쌓는다.

 

 

pop pop pop umm umm~

pop은 데이터를 꺼낸다.

어떻게? 마치 맨 위에 올려져있는 프링글스 과자처럼 꺼낸다.

 

 

3. top과 bottom

이때 가장 위에 있는(최근에 push한) 데이터를 top, 

가장 아래에 있는(가장 오래전 push한) 데이터를 bottom이라고 한다.

또 다른 예,

 

 

[코드]

(stack 라이브러리는 따로 존재하지 않지만 dequeue를 이용해서 stack처럼 사용하기도 한다.

이에 대해서 4. 블로그를 참고하면 된다.)

 

내가 구현한 기능은 4가지 이다.

1. push(Data data): stack에 data삽입
2. pop(): stack의 top에 있는 원소를 삭제
3. top(): stack의 top에 있는 원소를 출력 (삭제가 아니다)
4. bottom(): stack의 bottom에 있는 원소 출력

-> 모두 O(1)

 

class Stack:
  def __init__(self):
    self.stack = []

  def push(self, data):# stack 뒤에 원소 삽입
    self.stack.append(data)
    print(self.stack)

  def pop(self): # stack 뒤 원소 삭제
    self.stack.pop()
    print(self.stack)

  def top(self):
    print(self.stack[-1])

  def bottom(self):
    print(self.stack[0])



## __main__ ##
stack = Stack()
stack.push(2)
stack.push(4)
stack.push(6)
stack.top()
stack.pop()
stack.top()
stack.bottom()

->  main문을 실행하면 다음과 같은 결과가 나온다.

 

끄읏

 

[참고문헌]

1. 위키독스: https://wikidocs.net/192069

2. 블로그: https://cwjuns.tistory.com/18

3. 블로그: https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95

4. 블로그: https://velog.io/@yeseolee/Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack