Stack, Queue, deque

Stack

- 후입선출의 LIFO(Last In First Out) 구조

- 책이 쌓여있을때 맨 위에 책을 추가로 쌓는 것 = push(=append)
- 책을 위에서 내려다 보았을 때 가장 위에 있는 책을 확인하는 것 = peek
- 맨 위에 있는 책을 가져가는 것 = pop
- Python은 리스트 스택으로 사용 가능하도록 구현됨

-스택의 대표적인 활용은 인터넷 창 이전 페이지, 다음 페이지

class Stack(li):
    push = li.append

    def peek(self):
	return self[:-1]

s = Stack()

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

print('my stack is : ', s) # my stack is : [1, 2, 3]
print('제거 :',s.pop()) # 제거 : 3
print('my stack is : ', s) # my stack is : [1, 2]
print('맨 위에 : ', s.peek()) # 맨 위에 : 2

Queue

- 선입선출의 FIFO(First In First Out) 구조

- 컨베이어 벨트 위에 물건을 추가로 쌓는 것 = enqueue
- 컨베이어 벨트 위에서 맨 앞에 있는 물건을 확인하는 것 = peek
- 컨베이어 벨트 위에서 맨 앞에 있는 물건을 가져가는 것 = dequeue

from queue import Queue

q = Queue()
q.put(1)
q.put(2)
q.put(3)

print(q) # <queue.Queue object at 0x7f975d4a7710> (object로 인식)
print('my queue is : ', list(q.queue)) # my queue is : [1,2,3]
print('제거 :',q.get()) # 제거 : 1
print('my queue is : ', q.queue) # my queue is : [2,3]

deque

- from collections import deque

- stack과 queue의 장점을 모두 채택한 자료구조

- deque는 자료구조이므로 deque()로 객체를 생성해서 데이터 타입을 조회하면 deque로 인식

- deque 객체를 print로 출력하면 추가&삭제한 원소들이 출력되지 않고 객체가 출력되니 list로 변환해야 함

  (리스트로 변환하고 싶으면 list() 이용)

 

※ deque는 시간복잡도가 O(1)이고 list는 O(N)이라서 속도가 훨씬 효율적

 

※ 주요 메서드

- appendleft() = 맨앞에 원소 추가

- popleft() = 맨앞 원소 제거

- reverse() = 리스트의 정렬 순서 정반대로 변환

- append(), pop() = 맨 뒤에 원소 추가, 맨 뒤에 원소 제거