스택, 큐
-> 선형 자료구조
<스택(Stack)>
- LIFO - Last in First Out
가장 최근에 삽입(push)한 원소가 먼저 나온다(pop)
- 정해진 크기가 있다
Stack overflow : 더 이상 들어가지 못하는 상황에서 넣으려 할때 발생
Stack underflow : 빈 상태에서 더 빼려 할때 발생
#include <stdio.h>
struct Stack{
int data[100];
int len = 0; // 현재 스택 원소 개수
int capacity = 0; // 스택 용량
void create(int y){
capacity = y;
}
void push(int y){
if(len >= capacity){
printf("Starck overflow!\n");
}
else{
data[len++] = y; // y를 len에 넣고 그 다음 len++
}
}
void pop(){
// 맨 위 원소가 빠진다
if(len <= 0){
printf("Stack underflow!\n");
}
else{
data[len-1] = 0;
len--;
}
}
int top(){
// 스택의 가장 위에 있는 원소를 반환
// 스택에 아무것도 없다면 -1 출력
if(len <= 0)
return -1;
else
return data[len-1];
}
int size(){
// 스택 안에 들어있는 원소 개수 반환
return len;
}
};
int main() {
Stack s1;
s1.create(5); // 크기 5 스택 생성
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6); // overflow
printf("%d\n", s1.top()); // 5
s1.pop();
printf("%d\n", s1.top()); // 4
s1.push(6);
s1.push(7); // overflow
printf("%d\n", s1.top()); // 6
s1.pop();
s1.pop();
s1.pop();
s1.pop();
s1.pop();
s1.pop(); // underflow
printf("%d\n", s1.size());
return 0;
}결과 ->
Starck overflow!
5
4
Starck overflow!
6
Stack underflow!
0
<스택 라이브러리 사용 (in C)>
https://travelbeeee.tistory.com/69
참고 링크
<큐(Queue)>
- FIFO(First in First out)
- 먼저 삽입한 원소가 먼저 나온다
- 큐에도 크기 존재 -> queue overflow & queue underflow 존재
<큐 구현>
#include <stdio.h>
struct Queue{ // Queue 원소들은 모두 자연수라고 가정
// data 1 2 3 4
// f r
int data[100];
int front, rear; // rear - front = 현재 원소의 개수!!!
int capacity;
void create(int y){
capacity = y;
front = 0;
rear = 0;
}
void push(int x){
if(rear-front >= capacity)
printf("queue overflow\n");
else
data[rear++] = x; // rear도 하나 증가
}
void pop(){
if(rear-front <= 0)
printf("queue underflow\n");
else{
data[front] = 0;
front++; // front 증가
}
}
int returnFrontValue(){
// 큐의 맨 앞 원소 반환
// 없다면 -1 반환
if(rear-front <= 0)
return -1;
else
return data[front];
}
int returnQueueSize(){ // 큐 원소 개수 반환
return rear-front;
}
};
int main() {
Queue q1;
q1.create(3);
q1.push(1);
q1.push(2);
q1.push(3);
q1.push(4); // overflow
q1.push(5); // overflow
printf("%d\n", q1.returnFrontValue()); // 1
printf("%d\n", q1.returnQueueSize()); // 3
q1.pop();
q1.pop();
printf("%d\n", q1.returnFrontValue()); // 3
printf("%d\n", q1.returnQueueSize()); // 1
q1.pop();
q1.pop(); // underflow
printf("%d\n", q1.returnQueueSize()); // 0
return 0;
}<큐 구현의 문제점>
위에서 구현한 큐의 경우 front와 rear이 증가만 하므로 앞의 배열에 비는 공간이 생겨도 추가할 수가 없는 문제가 발생한다!
-->> 원형큐를 사용하자
<원형큐>
-> 앞 뒤가 없다 -->> 공간 활용 능력 우수
!!! 원형큐에서는 front와 rear의 차이로 현재 원소의 개수를 구할 수 없으므로 별도로 원소의 개수를 저장하는 변수를 선언하자 !!!
<원형큐 구현>
#include <stdio.h>
const int MAX = 10; // 배열 범위
// const = 상수 : 변경시킬 수 없다
struct Queue{ // Queue 원소들은 모두 자연수라고 가정
// data 1 2 3 4
// f r
int data[MAX]; // const 정의해서 사용하는 습관!
int front, rear; // rear - front = 현재 원소의 개수!!!
int capacity;
int numElement; // 원소 개수 기억
void create(int y){
capacity = y;
front = 0;
rear = 0;
numElement = 0;
}
void push(int x){
if(numElement >= capacity)
printf("queue overflow\n");
else{
/* data[rear++] = x;
if(rear >= MAX){ // 배열 범위 벗어날 시
rear = 0;
}
*/
data[rear] = x;
rear = (rear+1) % MAX; // 같은 표현
numElement++;
}
}
void pop(){
if(numElement <= 0)
printf("queue underflow\n");
else{
data[front] = 0;
front++; // front 증가
if(front >= MAX){ // 배열 범위 벗어날 시
front = 0;
}
numElement--;
}
}
int returnFrontValue(){
// 큐의 맨 앞 원소 반환
// 없다면 -1 반환
if(numElement <= 0)
return -1;
else
return data[front];
}
int returnQueueSize(){ // 큐 원소 개수 반환
return numElement;
}
};
int main() {
Queue q1;
q1.create(4);
for(int i = 0; i<100; i++){
q1.push(i);
q1.push(i+1);
q1.push(i+2);
q1.push(i+3);
q1.pop();
q1.pop();
q1.pop();
q1.pop();
}
q1.push(1);
q1.push(2);
printf("%d\n", q1.returnFrontValue());
q1.pop();
printf("%d\n", q1.returnFrontValue());
return 0;
}
매 순간 최선을 다하자