Python2 10일차 수업 정리_스택(Stack), 큐(Queue)

- 스택(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 = next

class 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