Python
Python2 10일차 수업 정리_스택(Stack), 큐(Queue)
어라연히프제
2024. 3. 20. 04:10
- 스택(Stack)
- 큐(Queue)
- 스택(Stack)
스택이란 데이터가 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조
== 후입선출, LIFO(Last In First Out)
스택의 ADT (추상 자료형)
- 맨 윗부분에 요소를 추가한다
- 맨 윗부분에 있는 요소를 알려준다
- 맨 윗부분에 있는 요소를 삭제하면서 알려준다
- 스택이 비어있는지 확인한다
- 스택을 깨끗이 비운다
스택의 주요함수
| push() | bottom 부터 차례대로 삽입된다. |
| pop() | top 부터 차례대로 삭제되며 top에 해당하는 값을 반환한다. |
| peek() | top에 있는 요소를 알려준다. |
| clear() | 스택에 있는 모든 요소를 삭제한다. |
연결리스트를 통한 스택 구현
우선 연결리스트의 Node 클래스 생성
# Node 클래스
class Node :
def __init__(self, data, link = None) :
self.data = data
self.link = link
stack 클래스 생성
# stack클래스
class StackWithLinked :
# 생성자(top을 초기화, 노드의 개수)
def __init__(self) :
# 마지막 노드 = 연결리스트의 head
self.top = None
# 노드의 개수
self.node_num = 0
# 스택이 비어있는 확인하는 메소드
def is_empty(self) :
return self.node_num == 0
# 스택에 데이터 추가하는 메소드
def push(self, data) :
# 새로운 노드 생성 => 새로운의 다음 노드는 기존의 top노드
node = Node(data, self.top)
# top노드 변경\
self.top = node
# 노드의 개수 증가
self.node_num += 1
# 확인 출력용 메소드
def show(self) :
node = self.top
while node is not None :
print(node.data)
node = node.link
print("======================")
# 스택에 데이터 삭제
def pop(self) :
# 비어있는 스택인지 확인
if self.is_empty() :
raise IndexError("빈 스택입니다")
# top 노드의 데이터를 변수에 저장
data = self.top.data
# 기존 top 노드를 삭제한 후 새로운 top 노드 지정
self.top = self.top.link
# 노드의 개수 감소
self.node_num -= 1
return data
# top요소 확인
def peek(self) :
# 스택이 비어있는지 확인
if self.is_empty() :
print("비어있는 스택입니다")
return
# top 노드의 데이터 반환
return self.top.data
# 검색(탐색) True, False
def search(self, data) :
# top노드부터 시작
node = self.top
# 처음 노드 다음까지 이동 -> 노드 == None
while node is not None :
if node.data == data :
return True
node = node.link
# 스택에서 data를 찾지 못할 경우
return False
stack 출력
stack = StackWithLinked()
# 스택이 비어있는지 확인
print(stack.is_empty())
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
stack.show()
# 스택이 비어있는지 확인
print(f"스택이 비어 있니? {stack.is_empty()}")
print() #줄바꿈
# 스택 데이터 삭제
print(f"삭제 데이터 : {stack.pop()}\n")
stack.show()
print(f"삭제 데이터 : {stack.pop()}")
print(f"삭제 데이터 : {stack.pop()}\n")
stack.show()
print(f"현재 top 노드 : {stack.peek()}")
# data에 2가 있는지 확인
print(stack.search(2))
# data에 100이 있는지 확인
print(stack.search(100))
- 큐(Queue)
큐란 스택과는 다르게, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조이다
== 선입선출, FIFO(First In First Out)형
큐의 구현은 배열을 이용한 - 순환 큐와 연결리스트를 이용한 - 링크드 큐로 구현 가능하다.
큐의 자료구조 용도는
: 데이터의 흐름을 제어하는데 사용된다.
(ex. 통신에서 메세지를 전송, 네트워크 트래픽 조절)
BFS => 그래프 자료구조에 사용되는 사용되는 대표적인 탐색 알고리즘 중 하나
활용 예시로는
스풀링 : 프린터의 출력처리
스케줄링 : 프로세스 관리 등 작업을 스케줄링
큐의 ADT (추상 자료형)
- 맨 끝에 요소를 추가한다
- 맨 앞의 요소를 삭제하면서 알려준다
- 맨 앞의 요소를 알려준다
- 큐가 비어있느지 확인한다
- 큐를 깨끗이 비운다
주요함수
| enqueue() | 큐 뒤쪽에 항목을 삽입한다 |
| dequeue() | 큐 앞쪽의 항목을 반환하고 제거한다 |
| peek/front() | 큐 앞쪽 항목을 조회한다 |
| empty() | 큐가 비어있는지 확인한다 |
| size() | 큐의 크기를 확인한다 |
필요연산
| creat(size) | 큐를 생성(초기화) |
| is_empty() | 큐가 비어있다면 True, 아니라면 False |
| is_full() | 큐가 가득차있다면 True, 아니라면 False |
| enqueue() | 큐에 데이터를 추가 |
| dequeue() | 큐에 데이터를 삭제 |
| peek() | 맨 처음 데이터를 반환 (dequeue에서 꺼내질 데이터) |
큐 예제
# 사용자 정의 함수
def queue() :
qu = []
qu.append(3)
qu.append(2)
qu.append(1)
print(qu)
while(qu) :
print(f"get value : {qu.pop(0)}")
# 함수호출
queue()
리스트 컴프리 헨션
# 리스트 컴프리 헨션
li = [None for i in range(5)]
print(li, type(li))
li1 = [i for i in range(5)]
print(li1, type(li1))
li2 = [i for i in range(1, 11) if i%2 == 0]
print(li2, type(li2))
큐의 ADT : 리스트를 통한 구현
class Queue :
# 생성자(que리스트, 요소 최대 개수, 큐의 요소 개수)
def __init__(self, max = 5) :
self.que = [None for i in range(max)]
self.max = max
self.rear = 0
# 큐가 비어있는지 확인
def isEmpty(self) :
return self.rear == 0
# 큐가 가득 차있는지 확인
def isFull(self) :
return self.max == self.rear #큐의 최대 용량 == 현재 큐의 요소 개수
# 큐의 데이터 삽입
def enqueue(self, element) :
# 큐가 가득 차있는지 확인
if self.isFull() :
print("큐가 가득 차 있습니다")
return
# 큐가 가득차있지 않다면
self.que[self.rear] = element
self.rear += 1
# 확인 출력용 메소드
def show(self) :
for i in range(self.rear) :
print(self.que[i], end = " | ")
print() #줄바꿈
# 큐데이터 삭제
def dequeue(self) :
# 비어있는 큐라면
if self.isEmpty() :
print("비어있는 큐")
return
# 큐가 비어있지 않다면
temp = self.que[0]
for i in range(self.rear - 1) :
self.que[i] = self.que[i+1] #리스트 요소들을 한칸 씩 앞으로 옮김
# print(self.que[i])
self.rear -= 1
return temp
# front확인
def peek(self) :
if not self.isEmpty() :
return self.que[0]
# 큐의 데이터 전체 삭제
def clear(self) :
self.rear = 0
큐 출력
q = Queue()
print(f"큐가 비어있나요? {q.isEmpty()}")
print(f"큐가 가득차있나요? {q.isFull()}")
# 데이터 삽입
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.show()
q.enqueue(40)
q.enqueue(50)
q.show()
q.enqueue(60)
q.show()
# 데이터 삭제
print(f"삭제 : {q.dequeue()}")
q.show()
# 큐의 맨 앞 데이터(front)확인
print(q.peek())
# 전체 삭제
q.clear()
q.show()
큐의 ADT : 연결리스트를 통한 구현
#노드 생성
class Node :
def __init__(self, data, next = None) :
self.data = data
self.next = nextclass QueueWithLinkedList :
# 생성자
def __init__(self) :
# 노드의 개수
self.node_num = 0
# 데이터를 꺼내는 쪽(맨 앞)노드
self.front = None
# 데이터를 넣는 쪽(맨 뒤) 노드
self.rear = None
# 큐가 비어있는지 확인
def is_empty(self) :
return self.node_num == 0
# 확인 출력용 메소드
def show(self) :
# 비어있는지 확인
if self.is_empty() :
print("빈 큐입니다")
return
# 비어있지 않다면
node = self.front
print("================")
while node is not None :
print(node.data, end =" | ")
node = node.next
print("\n===============")
# 큐에 데이터 삽입
def enqueue(self, data) :
# 추가할 노드 생성
node = Node(data)
# 만약 빈 큐라면
if self.is_empty() :
# 다음에 꺼낼 노드가 현재 노드
self.front = node
else :
# 기존 노드와 추가하는 노드 연결
self.rear.next = node
# 추가한 노드가 마지막 노드
self.rear = node
self.node_num += 1
# 큐에 데이터 꺼내기 메소드
def dequeue(self) :
# 비어있는 큐라면
if self.is_empty() :
print("빈큐입니다")
return
# 비어있지 않다면 데이터를 꺼내고 front 변경
data = self.front.data
# 다음 노드가 front가 되어야 됨
self.front = self.front.next
self.node_num -= 1
return data
큐 출력
que = QueueWithLinkedList()
# enqueue() : 큐에 데이터 추가
que.enqueue(1)
que.enqueue(2)
que.enqueue(3)
que.show()
# dequeue() : 큐에 데이터 삭제
print(f"삭제되는 값 : {que.dequeue()}")
que.show()
2024.03.20