<스택이란?>
스택(Stack)이란 쌓아올린다는 의미다.
따라서 스택 자료구조라는 것은 접시를 쌓듯이, 자료를 차곡차곡 쌓아올린 형태의 구조를 말한다.
<스택의 구조>
흔히 스택을 FILO라고 한다. First In, Last Out이기 때문이다.
먼저 들어간 데이터가, 가장 늦게 나오는 것이 스택의 특징이다.
■ top : 현재 메모리의 위치와 데이터의 overflow · underflow 파악
■ Pop() : top을 통한 데이터의 삭제를 말함
■ Push() : top을 통한 데이터의 삽입를 말함
Pop이든 Push든 top이든, 이름은 관용적인 약속이다.
꼭 정해져있는 것은 아니지만, 이 규칙에 따라 프로그램을 작성하는 것이 좋다.
<스택의 기본예제>
#include<stdio.h>
#include<stdlib.h> // system("cls"); 화면 청소를 위한 헤더파일
#include<conio.h> // getch(); 를 위한 헤더파일
void init_stack(void); // top의 초기 값을 설정한다 void print_stack(void); // stack을 출력할 때 사용된다
#include<stdlib.h> // system("cls"); 화면 청소를 위한 헤더파일
#include<conio.h> // getch(); 를 위한 헤더파일
void init_stack(void); // top의 초기 값을 설정한다 void print_stack(void); // stack을 출력할 때 사용된다
int top; // overflow와 underflow를 판단하는 기준이 된다 int push(int t); // 데이터를 입력한다, 혹은 쌓는다 int pop(void); // 데이터를 삭제한다, 혹은 꺼낸다
#define MAX 5 // 메모리는 최대 5개로 제한 int stack[MAX];
void main()
{
int i,t;
init_stack();
printf("Input Data : %d개\n",MAX);
for(i=0;i<MAX;i++) // 예제를 위해 만든 소스라, 메인 부분은 다소 억지스런 부분이 있다
{
scanf("%d",&t);
push(t);
}
getch(); // 어느 문자든 입력받을 때까지 대기한다. 입력 데이터 확인을 위해 한번 넣어주었다
print_stack();
}
void init_stack(void)
{
top = -1;
}
int push(int t)
{
if(top>=MAX-1) // 4를 넘게되면 overflow이므로, 입력할 때 조건검사를 하게 된다
{
printf("stack overflow\n");
return -1;
}
stack[++top] = t;
return t;
}
int pop(void)
{
if(top<0) // 0보다 작게되면 underlfow이므로, 역시 조건검사를 실행한다
{
printf("stack underflow\n");
return -1;
}
return stack[top--];
}
void print_stack(void)
{
int i;
system("cls");
printf("stack contents:top->bottom\n");
if(top==-1)
printf("[stack empty]\n");
for(i=top;i>=0;i--)
{
printf("%d",stack[i]);
}
printf("\n");
}
<큐란 무엇인가?>
큐(Queue)란 입구와 출구가 다른 자료구조로서, 선입선출(First In, First Out)이라 하여 FIFO라고도 불린다.
말 그대로 먼저 온 사람이, 먼저 일을 마치고 나가는 것이다.
<큐의 구조>
■ front : 맨 앞을 나타내는 위치
■ rear : 맨 뒤를 나타내는 위치
■ enQueue : rear에서 이루어지는 삽입 연산을 나타냄
■ deQueue : front에서 이루어지는 삭제 연산을 나타냄
스택과 큐에서의 연산을 비교하자면 이렇다.
<큐의 기본예제>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 10
const int front = -1; // front는 변하지 않는 값이므로, const로 값을 고정시켜 놓았다
int rear;
int queue[MAX];
int rear;
int queue[MAX];
void init() // 초기 설정 부분, 위에서 초기화하지 않고 분리한 이유는 언제든 이 함수를 통해 초기화가 진행되도록 하기 위해서다
{
rear = -1;
}
{
rear = -1;
}
void enQueue()
{
if(rear==9) // 최대 값을 넘기면, 조건 검사를 통해 Overflow를 출력해준다
{
printf("\nQueue is Overflow, You can't Input Data");
getch();
}
else // 그렇지 않다면, 데이터를 입력한다
{
printf("\nInput Data : ");
scanf("%d",&queue[++rear]);
}
}
{
if(rear==9) // 최대 값을 넘기면, 조건 검사를 통해 Overflow를 출력해준다
{
printf("\nQueue is Overflow, You can't Input Data");
getch();
}
else // 그렇지 않다면, 데이터를 입력한다
{
printf("\nInput Data : ");
scanf("%d",&queue[++rear]);
}
}
void deQueue()
{
if(rear==front) // rear와 front가 같아지면, 데이터가 없는 것이므로 조건 검사를 실행
{
printf("\nData Empty, Please Input Data");
getch();
}
else // 아니면 rear의 위치를 감소시킨다
{
--rear;
}
}
{
if(rear==front) // rear와 front가 같아지면, 데이터가 없는 것이므로 조건 검사를 실행
{
printf("\nData Empty, Please Input Data");
getch();
}
else // 아니면 rear의 위치를 감소시킨다
{
--rear;
}
}
void print() // 출력부분, 원래는 따로 있으나, 원활한 확인을 위해 입력과 삭제 부분에도 출력이 되도록 하였다
{
int i;
system("cls");
for(i=front+1 ; i<=rear ; i++)
{
printf("%d\t",queue[i]);
}
printf("\n\nrear : %d\n",rear);
printf("front : %d",front);
}
{
int i;
system("cls");
for(i=front+1 ; i<=rear ; i++)
{
printf("%d\t",queue[i]);
}
printf("\n\nrear : %d\n",rear);
printf("front : %d",front);
}
void main()
{
int sel;
init();
while(1)
{
printf("\n\n1.put 2.get 3.print \n\n");
printf("Select Number : ");
scanf("%d",&sel);
switch(sel)
{
case 1:
enQueue(); system("cls"); print(); break; // 원래는 print()가 없는 것이나
case 2:
deQueue(); system("cls"); print(); break; // 예제의 확인을 위해 넣어놓았다
case 3:
print(); break;
default:
system("cls");
{
int sel;
init();
while(1)
{
printf("\n\n1.put 2.get 3.print \n\n");
printf("Select Number : ");
scanf("%d",&sel);
switch(sel)
{
case 1:
enQueue(); system("cls"); print(); break; // 원래는 print()가 없는 것이나
case 2:
deQueue(); system("cls"); print(); break; // 예제의 확인을 위해 넣어놓았다
case 3:
print(); break;
default:
system("cls");
printf("Fail Your Number");
}
}
}
}
}
}
.
