[파이썬/자료구조] 스택(stack)

[파이썬/자료구조] 스택(stack)

 

LIFO(Last In First Out) 방식.

후입 선출이라고도 하며, 가장 먼저 들어간 값이 맨 아래에 깔린다.

가장 나중에 넣은 데이터를 가장 먼저 빼낼 수 있다.

프링글스 통에서 과자를 추가하고 꺼내는 형태와 같다.

 

 

스택 구조의 연산

Push : 스택에 값 추가.

Pop : 스택 가장 마지막 원소를 삭제하고 반환.

Peek : 스택 가장 마지막 원소를 반환.(삭제 x)

Empty : 스택이 비어있으면 1, 아니면 0을 반환한다.

 

덱 라이브러리를 사용하면 리스트로 구현한 것보다 훨씬 빠르다. 

from collections import deque

dq=deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 제거
dq.appendleft() # 덱의 가장 왼쪽에 원소 삽입
dp.pop() # 가장 오른쪽 원소 제거
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산

from collections import deque

stack = deque([1, 2, 3])
stack.append(4)    // Push
print(stack)

stack.pop()    // Pop
print(stack)

stack.appendleft(5)
print(stack)

stack.popleft()
print(stack)

top = stack[-1]		// Peek, 가장 마지막 값을 제거하지 않고 반환한다.
print(top)

deque([1, 2, 3, 4])
deque([1, 2, 3])
deque([5, 1, 2, 3])
deque([1, 2, 3])
3

 

from collections import deque

def isEmpty(dq):    # Empty, 스택이 비어있으면 True, 값이 있으면 false 반환
    return not dq

stack = deque([1, 2, 3])
stack2 = deque()

print(isEmpty(stack))
print(isEmpty(stack2))

False
True