스택(Stack) & 큐(Queue)

1. 스택(Stack)

- LIFO(Last-In, First-Out) 구조 : 먼저 들어간 것이 나중에 나온다.

 

- 스택 관련 연산

1) push : 데이터 추가

2) pop : 데이터 꺼내기

 

- 소스코드

1) 배열로 Stack 구현

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

typedef struct ArrStack {
	int arr[100];
	int top;
}Stack;

void init(Stack* node);
int is_Empty(Stack* node);

void push(Stack* node, int data);
int pop(Stack* node);

int main() {
	Stack my_stack;
	int n;

	init(&my_stack);

	for (int i = 0; i < 3; i++) {
		scanf("%d", &n);
		push(&my_stack, n);
	}	
	while (!is_Empty(&my_stack)) {
		printf("%d ", pop(&my_stack));
	}

	return 0;
}

//stack 초기화
void init(Stack* node) {
	node->top = -1;
}
//stack 비었는지 확인
int is_Empty(Stack* node) {
	if (node->top == -1)
		return 1;
	else
		return 0;
}
//stack에 데이터 추가
void push(Stack* node, int data) {
	node->top++;
	node->arr[node->top] = data;
}
//stack에서 데이터 꺼내기
int pop(Stack* node) {
	int temp;

	if (is_Empty(node)) {
		printf("Stack Memory Error\n");
		exit(-1);
	}

	temp = node->arr[node->top];
	node->top--;
	return temp;
}

 

2) linked list로 Stack 구현

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

typedef struct node {
	int data;
	struct node* pre;
}Node;

typedef struct listStack {
	Node* head;
}Stack;

void init(Stack* node);
int is_Empty(Stack* node);

void push(Stack* node, int data);
int pop(Stack* node);

int main() {
	Stack my_stack;
	int n;

	init(&my_stack);

	for (int i = 0; i < 3; i++) {
		scanf("%d", &n);
		push(&my_stack, n);
	}	
	while (!is_Empty(&my_stack)) {
		printf("%d ", pop(&my_stack));
	}

	return 0;
}

//stack 초기화
void init(Stack* node) {
	node->head = NULL;
}

int is_Empty(Stack* node) {
	if (node->head == NULL)
		return 1;
	else
		return 0;
}

void push(Stack* node, int data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->pre = node->head;

	node->head = newNode;
}

int pop(Stack* node) {
	int temp, rnode;

	if (is_Empty(node)) {
		printf("Stack Memory Error\n");
		exit(-1);
	}

	temp = node->head->data;
	rnode = node->head;

	node->head = node->head->pre;
	free(rnode);
	return temp;
}

 

 

2. 큐(Queue)

- FIFO(First-In, First-Out) 구조 : 먼저 들어간 것이 먼저 나온다.

 

- 큐 관련 연산

1) enqueue : 데이터 추가

2) dequeue : 데이터 꺼내기

 

- 원형 큐 : 배열로 생각하면, 한 배열이 끝나고 다음에 배열의 시작점으로 이어진다고 본다.

* Empty일 때와 Full일 때를 구분하기 위해 배열을 모두 채우지 않는다.

한 칸을 비우기로 했으니까, 아래의 그림이 Empty인 상태가 된다.

 

- 소스코드

1) 배열로 원형 queue 구현

#include <stdio.h>
#include <stdlib.h>
#define QUELEN 5

typedef struct cQueue {
	int front;
	int rear;
	int data[QUELEN];
}Queue;

void init(Queue* cq);
int is_Empty(Queue* cq);
int nextIdx(int p);

void enqueue(Queue* cq, int data);
int dequeue(Queue* cq);

int main() {
	Queue my_cq;
	int n;

	init(&my_cq);
	for (int i = 0; i < 6; i++) {
		scanf("%d", &n);
		enqueue(&my_cq, n);
	}

	while (!is_Empty(&my_cq)) {
		printf("%d ", dequeue(&my_cq));
	}

	return 0;
}

void init(Queue* cq) {
	cq->front = 0;
	cq->rear = 0;
}

int is_Empty(Queue* cq) {
	if (cq->front == cq->rear)
		return 1;
	else
		return 0;
}

int nextIdx(int p) {
	if (p == QUELEN)//마지막 인덱스의 다음은 인덱스 0부터 다시 시작
		return 0;
	else
		return p + 1;
}

void enqueue(Queue* cq, int data) {
	if (nextIdx(cq->rear) == cq->front) {
		printf("Queue is FULL\n");
		exit(-1);
	}

	cq->rear = nextIdx(cq->rear);
	cq->data[cq->rear] = data;
}

int dequeue(Queue* cq) {
	if (is_Empty(cq)) {
		printf("Queue is Empty\n");
		exit(-1);
	}
	
	cq->front = nextIdx(cq->front);
	return cq->data[cq->front];
}