1주차 스택/큐

스택/큐

😎 스택 (Stack - 쌓다)

   프로그래밍에서 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조
   LIFO(Last-In, First-Out) 가 기본원리
   내장함수 : push, peek, pop
   스택 자료구조 : 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말함

       books = [book1, book2, book3] + [book4] ← push
       books = [book1, book2, book3, book4] ← 마지막 삽입을 확인 peek
       books = [book1, book2, book3] / [book4] ← 마지막 삽입한 것을 삭제 pop

 

즉, 스택에서 삽입하는 연산을 push , 삽입한 것을 확인하는 연산 peek , 삭제하는 연산을 pop 이라고 한다.
스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조적인 특징을 가지고있다.

 

✔ PYTHON 스택의 구현방법

□ 직접구현

 

class Stack(list):
	push = list.append #append 는 리스트에서 마지막에 자료를 추가하는 것 push와 동일
	def peek(self):
		return self[-1] #가장 마지막에 있는 값을 선택
				# self[len(self)-1] 위와 동일
 # Pop은 list의 내장함수로 이미 존재한다.

□ 직접구현 활용

s = Stack()
s.push(1)
s.push(5)
s.push(10)

print("my stack is : ", s)
    # my stack is : [1, 5, 10]
    
print("popped value is : " , s.pop())
    # popped value is : 10
    
print("my stack is : ", s)
    # my stack is : [1, 5] # pop 을 했기 때문에 더이상 10은 없음
    
print("peeked value is : ", s.peek())
    # peeked value is : 5 # peek은 보여지기만 할 뿐 데이터를 추출하진 않음
    
print("my stack is : ", s)
    # my stack is : [1, 5]

□  List를 스택으로 구현

 

s =[]
s.append(1)
s.append(5)
s.append(10)

print("my stack is : ", s)
    # my stack is : [1, 5, 10]
    
print("popped value is : " , s.pop())
    # popped value is : 10
    
print("my stack is : ", s)
    # my stack is : [1, 5]
    
print("peeked value is : ", s[-1]) #인덱스 값을 이용해 peek 확인
    # peeked value is : 5
    
print("my stack is : ", s)
    # my stack is : [1, 5]

□ 스택의 활용

   이전페이지, 다음페이지
   깊이 우선 탐색 (DFS)


😎 큐 (Queue - 일이 처리되기를 기다리는 리스트)

  프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조
  FIFO(First-In, First-Out)가 기본원리 = 선착순 방식
  내장함수 : put, peek, get
  큐 자료구조 : 컨베이어 벨트

 

     BOX리스트 [BOX1, BOX2, BOX3]
     Put → [BOX1, BOX2, BOX3, BOX4]
     Peek -> [BOX1, BOX2, BOX, BOX4] # 첫번째 담은 박스가 무엇인지 알 수 있음,, 확인만 할뿐
     Get -> [BOX1/ BOX2, BOX, BOX4] # 첫번째 담은 박스가 빠져나감

 

큐는 놀이동산에서 줄을 서서 기다리는 것처럼 먼저들어온 자료가 먼저 나가는 자료구조를 말함
큐는 한쪽에서 삽입과, 삭제가 이루어지는 스택과 달리 삭제연산만 수행되는 곳과, 삽입연산만 수행되는 곳으로 나뉘어져 있다.

✔ PYTHON 큐의 구현방법

□  직접구현

 

class Queue(list):
	put = list.append
	def peek(self):
		return self[0] # 가장 앞에 있는 값을 보기 위해
	def get(self):
		return self.pop(0) # pop의 파라미터 값을 0을 주게되면 인덱스값이 [0]를 추출할 수 있다.

 

□  직접구현 활용

 

q = Queue()
q.put(1)
q.put(5)
q.put(10)

print("my queue is : ", q)
    # my queue is : [1,5,10]
    
print("removed value is : ", q.get())
    # removed value is : 1
    
print("my queue is : ", q)
    # my queue is : [5,10]
    
print ("peeked value is : ", q.peek()) # 데이터 확인만 함
    # peeked value is : 5
    
print("my queue is : ", q)
    # my queue is : [5,10]

□ 이미 구현된 클래스 import

 

from queue import Queue

q = Queue()
q.put(1)
q.put(5)
q.put(10)

print("my queue is : ", q)
    # my queue is : [1,5,10]
    
print("removed value is : ", q.get())
    # removed value is : 1
    
print("my queue is : ", q)
    # my queue is : [5,10]
    
print ("peeked value is : ", q.peek()) # 데이터 확인만 함
    # peeked value is : 5
    
print("my queue is : ", q)
    # my queue is : [5,10]

□  List를 큐로 구현

 

q =[]
q.append(1)
q.append(5)
q.append(10)

print("my queue is : ", q)
    # my queue is : [1, 5, 10]
    
print("removed value is : ", q.get())
    # removed value is : 1
    
print("my queue is : ", q)
    # my queue is : [5,10]
    
print ("peeked value is : ", q[0]) # 데이터 확인만 함
    # peeked value is : 5
    
print("my queue is : ", q)
    # my queue is : [5,10]

□ 큐의 활용

  프린터 인쇄 대기열
  너비 우선 탐색 (BFS)