Stack, Queue, Deque ( 스택, 큐, 덱 )

✔️ Stack ( 스택 )

◾ 먼저 들어간 데이터가 나중에 나오는 자료구조

◾ LIFO ( Last-In, First-Out )

◾ 후입선출 ( 後入先出 )

⏱️ 시간복잡도

◾ Push : O(1)

◾ Pop : O(1)

 

💾 소스 코드

#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

int stack[STACK_SIZE];
int top = -1;

void push(int item) {
	if (top >= STACK_SIZE - 1) {
		printf("Stack is Full.\n");
		return;
	}
	
	stack[++top] = item;
}

int pop() {
	if (top == -1) {
		printf("Stack is Empty.\n");
		return 0;
	}
	
	return stack[top--];
}

int peek() {
	if (top == -1) {
		printf("Stack is Empty.\n");
		return 0;
	}

	return stack[top];
}

void printStack() {
	int i;

	for (i = 0; i <= top; i++)
		printf("%d ", stack[i]);
	puts("");
}

int main() {
	push(1);
	push(2);
	push(3);
	push(4);

	printStack(); // 1 2 3 4

	pop();
	pop();

	printStack(); // 1 2

	push(5);
	push(6);

	printStack(); // 1 2 5 6
	
	printf("stack top = %d", peek());

	return 0;
}

 

👀 시각화

---

✔️ Queue(큐)

◾ 먼저 들어간 데이터가 먼저 나오는 자료구조

◾ FIFO(First-In, First-Out)

◾ 선입선출 ( 先入先出 )

 

⏱️ 시간복잡도

◾ Enqueue : O(1)

◾ Dequeue : O(1)

 

💾 소스 코드

---

✔️ Stack, Queue 응용

1️⃣ Stack으로 Queue 만들기

 

2️⃣ Queue로 Stack 만들기

 

https://medium.com/@circlee7/%EB%91%90%EA%B0%9C%EC%9D%98-%ED%81%90%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%8A%A4%ED%83%9D-7cacfcf612ea

두개의 큐로 구현하는 스택

3️⃣ 후위 표기법 수식 변환과 연산

 

---

✔️ Deque( 덱 )

◾ 덱은 양방향으로 데이터를 넣고 뺄 수 있는 자료구조이다.

⏱️ 시간복잡도

◾ push_front : O(1)

◾ push_back : O(1)

◾ pop_front : O(1)

◾ pop_back : O(1)

 

💾 소스 코드