[python/자료구조] 스택(Stack), 큐(Queue)에 대해서

 

스택(Stack)이란?

---

쌓다 라는 의미를 가지며 LIFO(Last In First Out) 후입선출 구조를 가진다.

삽입 : push
삭제 : pop

 

Python Stack 직접 구현

---

 
  >>> s = [ ]
  >>> s.append(1)
  >>> s.append(5)
  >>> s.append(10)
  >>> print("my stack : ", s)
  my stack : [ 1, 5, 10 ]
  >>> print(s.pop())
  10
  >>> print("my stack : ", s)
  my stack : [ 1, 5 ]
  >>> print(s[-1])
  5
  >>> print("my stack : ", s)
  my stack : [ 1, 5 ]
   

list.pop( ) : 리스트의 마지막 인덱스 값을 리턴 후 삭제

list[-1] : 리스트의 마지막 인덱스 값 추출

 

스택(Stack)의 활용

---

 - 웹브라우저의 이전 페이지, 다음 페이지
 - 깊이 우선 탐색(DFS)
 - 역순 문자열 (나중에 입력된 문자부터 출력)

 

---

 

큐(Queue)란?

---

일이 처리되기를 기다리는 list를 의미하며 FIFO(First in First Out) 선입선출 구조를 가진다.

삽입 : put
삭제 : get

 

Python Queue 직접 구현

---

 
  >>> q = [ ]
  >>> q.append(1)
  >>> q.append(5)
  >>> q.append(10)
  >>> print("my queue : ", q)
  my queue : [ 1, 5, 10 ]
  >>> print(q.pop(0))
  1
  >>> print("my queue : ", q)
  my queue : [ 5, 10 ]
  >>> print(q[0])
  5
  >>> print("my queue : ", q)
  my queue : [ 5, 10 ]
  

list.pop(0) : 리스트의 첫 번째 인덱스 값을 리턴 후 삭제

list[0] : 리스트의 첫 번째 인덱스 값 추출

 

큐(Queue)의 활용

---

  - 프린터 인쇄 대기열
  - 너비 우선 탐색(BFS)
  - 은행 업무, 콜센터 대기