[자료구조] 스택(STACK)과 큐(QUEUE)

➕ STACK

LIFO (Last Input First Out)

• 마지막에 넣은 원소가 먼저 나온다는 것이다.

• 아래가 막혀있고 위가 뚫린 형태로써, 차곡차곡 쌓는 구조이다.

• 스택에서 삽입은 PUSH, 삭제는 POP 이라는 용어로 사용한다.

• DFS 탐색시 사용

  ex) 문서 작업에서 컨트롤 + Z 와 같은 이전 상태로 되돌리기 등처럼 캐시와 같은 모습으로 많이 존재한다.

😨 stack overflow?

• stack이란 것을 배우기도 전부터 많이접해보았을 것이다.
• 말 그대로, 위와 같이 정해진 크기에 무언가를 계속 넣고 있다가 받아들일 수 있는 크기를 초과해서 흘러넘쳐버린 것을 말한다.

코드(연결리스트 이용, c로 구현)

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

typedef struct Node {
    char* data;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct LinkedListStack {
    Node* top;
    int size;
} LinkedListStack;


LinkedListStack* init() {
    LinkedListStack* stack;
    stack = (LinkedListStack*)malloc(sizeof(LinkedListStack));
    stack->top = NULL;
    stack->size = 0;
    return stack;
}

Node* NodeInit(char* str) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = (char*)malloc(strlen(str)+1);
    strcpy(newNode->data, str);
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void push(LinkedListStack* list, char* str) {
    Node* newNode = NodeInit(str);
    Node* oldTop;

    if(list->top == NULL) {
        list->top = newNode;
    }
    else {
        oldTop = list->top;
        oldTop->next = newNode;
        newNode->prev = oldTop;
        list->top = newNode;
    }
    list->size++;
}

void pop(LinkedListStack* list) {
    Node* currentTop = list->top;
    Node* newTop;

    if(currentTop == NULL) return;
    else {
        newTop = list->top->prev;
        newTop->next = NULL;
        list->top = newTop;
    }
    list->size--;
    free(currentTop->data);
    free(currentTop);
}

Node* Top(LinkedListStack* list) {
    return list->top;
}

➕ Queue

FIFO (First Input First Out)

• 가장 현생활에서 많이 쓰이는 구조이다.
• 먼저 줄 선 사람이 먼저 계산을 하는 것이다.
• 큐에서 삽입은 EnQueue, 삭제는 DeQueue 이라는 용어로 사용한다.
• BFS 탐색에서 사용

👉 코드 (연결리스트 이용 , c 로 구현)

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

typedef char element;

typedef struct QNode {
	element data;
	QNode* link;
}QNode;
typedef struct LinkedQueue {
	QNode* front;
	QNode* rear;
}LinkedQueue;

LinkedQueue* createLinkedQueue() {
	LinkedQueue* LQ = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	LQ->front = NULL;
	LQ->rear = NULL;
	return LQ; 
}
int isEmpty(LinkedQueue* LQ) {
	if (LQ->front == NULL) return 1;
	else return 0;
}
void enQueue(LinkedQueue* LQ, element item) {
	QNode* new = (QNode*)malloc(sizeof(QNode));
	new->data = item;
	new->link = NULL;
	if (LQ->front == NULL) {
		LQ->front = new;
		LQ->rear = new;
	}
	else {
		LQ->rear->link = new;
		LQ->rear = new;
	}
}
element deQueue(LinkedQueue* LQ) {
	if (isEmpty(LQ)) exit(1);
	else {
		QNode* old = LQ->front;
		element item = LQ->front->data;
		LQ->front = LQ->front->link;
		if (isEmpty(LQ)) LQ->rear = NULL;
		free(old);
		return item;
	}
}