3장 - 스택(Stack)과 큐(Queue)

순서화 리스트의 종류 중 스택,큐가 있다.

 

스택(Stack)

 삽입과 삭제가 'top'이라 불리는 한 쪽 끝 지점에서 발생하는 순서화 리스트

 

시스템 스택(Run-time Stack)

 시스템에서 함수 호출을 처리하기 위해 사용

 재귀함수 호출의 성능과 관련

 

스택의 구현

#include <stdio.h>
#define MAX_SIZE 101

typedef struct {
	int key;
}element;

element stack[MAX_SIZE];
int top = -1; //top을 -1로 초기화하였음.

bool IsEmpty() {
	if (top < 0)
		return true;
	else
		return false;
}

bool IsFull() {
	if (top >= MAX_SIZE - 1)
		return true;
	else
		return false;
}

void push(element item) {
	if (IsFull()) { //top >= MAX_SIZE-1
		return; //더이상 넣을 수 없음
	}
	stack[++top] = item;

}

element pop() {
	if (IsEmpty()) { //top < 0 , 스택이 빈 경우
		return;
	}
	return stack[top--]; //stack[top]을 리턴하고 top을 1 감소시킴
}

처음 top을 초기화할 때 -1로 하냐 0으로 하냐에 따라

isFull, isEmpty, push,pop 함수를 조금씩 손봐줘야한다

top을 먼저 1 증가시키고 실행할건지, 실행시키고 1증가시킬건지

이런 부분만 수정하면 된다

 

 

---

큐(Queue)

 삽입과 삭제가 다른 쪽에서 발생하는 순서화 리스트

삽입이 발생하는 위치: rear

삭제가 발생하는 위치: front

 

#include <stdio.h>
#define MAX_SIZE 101

typedef struct {
	int key;
}element;

element queue[MAX_SIZE];
int rear = -1;
int front = -1;

bool isEmpty() {
	if (front == rear)
		return true;
	else
		return false;
}

bool isFull() {
	if (rear == MAX_SIZE - 1)
		return true;
	else
		return false;
}

void addq(element item) {
	if (isFull()) {// rear == MAX_SIZE -1인 경우
		return; //가득차서 더이상 못넣음
	}
	queue[++rear] = item; //rear 1증가시키고, item 삽입
}

element deleteq() {
	if (isEmpty()) {// rear == front인 경우
		return; //빈 큐라서 못 뺌
	}
	return queue[++front]; //front를 1 증가시키고 큐에서 front위치의 값 리턴
}

---

원형 큐

기존 큐에서 빈 공간이 있어도 사용을 못 하는 경우가 있었다

이를 효율적으로 쓰기 위해 큐의 시작과 끝을 연결한 형태로 만듦(%연산자 이용)

 

큐가 비어있는 상태가 front==rear 였는데

원형 큐에서 큐가 가득 찬 상태가 되면 똑같이 front==rear가 된다

빈 상태와 가득 찬 상태를 구분하기 위해, 큐를 가득 채우지 않고 큐 크기의 -1까지만 채우기로 하자.

void addq(element item) {
	if ((rear+1)%MAX_SIZE == front) {
		return; //가득차서 더이상 못넣음
	}
	rear = (rear + 1) % MAX_SIZE;
	queue[rear] = item; 
}

element deleteq() {
	if (front==rear) {// rear == front인 경우
		return; //빈 큐라서 못 뺌
	}
	front = (front + 1) % MAX_SIZE;
	return queue[front];
}