[자료구조] 스택,큐

 

 

---

1. 스택

---

 

 

https://velog.io/@yeonjuu417/%EC%8A%A4%ED%83%9D-%ED%81%90

 

 

스택은 데이터가 아래에서부터 쌓이고

데이터를 꺼내려면 위에서부터 빼야 하는 

LIFO(Last In First Out) 구조를 가지는 자료구조입니다.

 

흔히 쟁반 쌓기, 빨래통에 비유가 되는 이 스택 자료구조는

 

 

 

파워포인트나 word 또는 다양한 프로그램의 되돌리기(ctrl + z), 다시 하기(ctrl + y) 에 쓰입니다

ctrl  + z 사용하면 가장 먼저 실행한 명령보다

가장 최근에 실행한 명령을 취소해야 하니까요.

 

이외에도 많은 부분에 쓰이는 자료구조라서 반드시 배워야 합니다.

 

스택이라는 자료 구조에서 구현해야할 기능은 다음과 같습니다.

 

push(data) : 맨 앞에 데이터 넣기

pop() : 맨 앞의 데이터를 뽑으면서 그것을 반환해주기

peek() : 맨 앞의 데이터 보기

isEmpty() : 스택이 비었는지 안 비었는지 여부 반환해주기

 

 

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:

    def __init__(self):
        self.head = None

    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head
        return

    def pop(self):
        if self.is_empty():
            return "Stack is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head

    def peek(self):
        if self.is_empty():
            return "Stack is Empty"
        return self.head.data

    def is_empty(self):
        return self.head is None

stack = Stack()
stack.push(3)
print(stack.peek())		# 3
stack.push(4)
print(stack.peek())		# 4
print(stack.pop().data) 	# 4
print(stack.peek())		# 3

 

stack은 LinkedList로 구현할 수 있으며

파이썬의 동적 배열인 List로도 사용할 수 있습니다

 

 가장 중요한 것은 최근에 저장한 데이터를 head로 가리키는 것입니다.

pop이나 peek 함수가 호출되면 바로 최근 저장한 데이터를 빼낼 수 있게 말이죠

 

 

마지막으로 넣은 카트를 먼저 사용할 수 있다.

 

 

 

---

2. 큐

---

 

 

https://velog.io/@godkor200/%ED%81%90Queue

 

 

큐는 스택과는 달리

먼저 저장한 데이터를 먼저 뽑는

FIFO(First In First Out) 특성을 띠는 자료구조입니다.

 

큐라는 자료 구조에서 구현해야할 기능은 다음과 같습니다.

 

enqueue(data) : 맨 뒤에 데이터 추가하기 

dequeue() : 맨 앞의 데이터 뽑기 

peek() : 맨 앞의 데이터 보기 

isEmpty() : 큐가 비었는지 안 비었는지 여부 반환해주기

 

 

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return "Queue is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    def peek(self):
        if self.is_empty():
            return "Queue is Empty"
        return self.head.data

    def is_empty(self):
        return self.head is None

queue = Queue()
queue.enqueue(3)
queue.enqueue(4)
queue.dequeue()
queue.enqueue(5)
print(queue.peek())	# 4

 

큐도 LinkedList로 구현할 수 있다.

큐는 스택과는 달리

맨 앞 쪽과 맨 뒷 쪽을 기억해줘야 한다.

넣는 방향과 나가는 방향이 서로 다르기 때문이다.

 

먼저 기다린 사람이 먼저 코로나 검사를 받을 수 있다