[1주차] 자료구조 - 스택/큐

1주차 알고리즘 TIL

 

✍ PlayData 1주차 스택/큐 수강 후 기록

 

스택(Stack)

스택 자료구조는 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조 이다.
프로그래밍에서 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조
LIFO(Last-In, First_Out)가 기본 원리
Push, Peek, Pop 이라는 내장함수가 있다.
Push : 리스트에 Data 추가
Peek : 마지막에 추가 된 Data 확인
Pop : 처음 추가 된 Data 삭제

 

 

Python 스택의 구현 방법 - (ex) 인터넷에서의 이전페이지, 다음페이지, 깊이 우선 탐색(DFS))

직접구현

class Stack(list):
            push = list.append
            def peek(self):
                return self[-1]
                    self[len(self)-1]​
                    
                    
# Pop은 내장함수로 이미 가지고 있음

이미 구현된 클래스 import (X)
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])            peeked value is : 5
print("my stack is : ", s)                    my stack is : [1, 5]

 

 

 

큐(Queue)

'일이 처리되기를 기다리는 리스트' 라는 의미
프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조로
FIFO(First-In, First-Out)가 기본원리
놀이동산에서 줄을 서서 기다리는 것처럼 먼저 들어온 자료가 먼저 나가는 자료구조
한쪽에서 삽입과 삭제가 이루어지는 스택과 달리 삭제 연산만 수행되는 곳과, 삽입 연산만 수행되는 곳으로 나뉘어짐
Put, Peek, Get 이라는 내장 함수가 있다.
Put : 리스트에 Data 추가
Peek : 가장 먼저 들어간 Data 확인
Get : 가장 먼저 들어간 Data 가져감

 

Python 큐의 구현 방법 - (ex) 프린터 인쇄 대기열, 너비 우선 탐색(BFS))

직접 구현

class Queue(list):
              put = list.append
              def peek(self):
                  return self[0]
              def get(self):
                  return self(0)​

이미 구현된 클래스

import from queue import Queue
                          q = Queue()
                          q.put(1)
                          q.put(5)
                          q.put(10)
                          print ("my queue is : ", q)
                          print ("removed value is : ", q.get())
                          print ("peeked value is : ", q)
                          print ("my queue is : ", q)​

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.pop(0))        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]