๐ก ์ ์
์คํ์ ํ์ชฝ์ผ๋ก๋ง ๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ ๋บ ์ ์๋ ํํ์ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ก, ํ์
์ ์ถ(Last In First Out, LIFO)์ด๋ผ๋ ํน์ฑ์ ์ง๋๊ณ ์๋ค.
์ฐจ๊ณก์ฐจ๊ณก ์์ฌ ์๋ ํํ์ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ผ๊ณ ๋ณด๋ฉด ๋๋ค.
๐ฑ ADT
์คํ์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ํ์ชฝ์ผ๋ก๋ง ๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ (push), ๋บ(pop) ์ ์๋ค. ์คํ์ ์ผ๋ฐ์ ์ผ๋ก ์๋ฃ๋ฅผ ๋ฃ๊ณ ๋นผ๋ ๊ฒ๋ฟ๋ง ์๋๋ผ ๊ฐ์ฅ ์์ ์๋ ์๋ฃ๋ฅผ ํ์ธ(peek)ํ๊ฑฐ๋, ์คํ์ด ๋น์ด(isEmpty)์๋์ง ํ์ธํ ์ ์๋ค.
์คํ์ ํ์ํ ๊ธฐ๋ฅ๋ค์ด ์ด๋ ์ ๋ ๋์ด๋์๋๋ฐ, ์ถ์ ์๋ฃํ์ ๊ฐ๋ตํ๊ฒ ์ฝ๋๋ก ํํํด๋ณด์.
Stack<T> {
push(T);
pop();
peek();
isEmpty();
}
์ด๋ ์ ๋ ์ ๋ฆฌ๋์์ผ๋ ์ด๋ฅผ C์ธ์ด๋ก ๊ตฌํํด๋ณด์.
๐ ์คํ ์ดํด๋ณด๊ธฐ
์คํ์ ๊ตฌํํ ์ ์๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ง๋ง ์ด๋ฒ ๊ธ์์๋ ๋ฐฐ์ด(Array)์ ํ์ฉํ์ฌ ์คํ์ ๊ตฌํํ๋ ค๊ณ ํ๋ค. ์๋ ์์ ์ฝ๋๋ฅผ ํ์ธํด๋ณด์.
#define STACK_SIZE 10
int top = -1;
int stack[STACK_SIZE];
STACK_SIZE ๋ผ๋ ๋งคํฌ๋ก๋ฅผ ์ ์ํ๋ค.
์คํ์ ํฌ๊ธฐ๋ฅผ 10์ผ๋ก ์ ์ํ ๊ฒ์ด๊ธฐ ๋๋ฌธ์ 10์ด๋ผ๋ ๊ฐ์ผ๋ก ์ง์ ํด์ฃผ์๋ค.
top ์ด๋ผ๋ ์ ์ํ ๋ณ์์ stack ์ด๋ผ๋ ์ด๋ฆ์ ๋ฐฐ์ด์ด ์ ์ธ๋์ด์๋ค. ์ฉ๋๋ ์๋์ ๊ฐ๋ค.
- top: ์คํ ์ต์๋จ ์๋ฃ์ ์์น๋ฅผ ๋ํ๋ด๋ ๋ณ์
- stack: ์๋ฃ๋ฅผ ์ ์ฅํ ๋ฐฐ์ด (์คํ ๊ณต๊ฐ)
top ์ ์ด๊ธฐ ๊ฐ์ด -1์ธ ์ด์ ๋ ์์ง ์คํ์ด ๋น์ด์๊ธฐ ๋๋ฌธ์ด๋ค. ์ฆ -1์ ๋น์ด์๋ค(empty)๋ผ๋ ์๋ฏธ๋ก ๋ฐ์๋ค์ด๋ ค๊ณ ํ๋ค. ๋จผ์ ๊ธฐ๋ณธ์ ์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ , ๋บ ์ ์๋ ๊ธฐ๋ฅ์ ๊ตฌํํด๋ณด์.
void push(int);
int pop(void);
void push(int data)
{
// ๋ฐฐ์ด ์ธ๋ฑ์ค๋ 0๋ถํฐ ์์์ด๋ฏ๋ก, STACK_SIZE - 1
if (top >= STACK_SIZE - 1)
{
printf("๊ฝ ์ฐผ๋ค!");
return;
}
stack[++top] = data;
}
int pop(void)
{
if (isEmpty())
{
printf("ํ
๋น์ด์๋ค");
return 0;
}
return stack[top--];
}
๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ ๋บ ๋ ์คํ์ด ๊ฐ๋ ์ฐผ๋์ง, ์๋๋ฉด ๋น์ด์๋์ง ํ์ธํ ์ ์๋๋ก ์กฐ๊ฑด์ด ์ถ๊ฐ๋์ด์๋ค.
์ฌ๊ธฐ์ ์ฃผ์ ๊น๊ฒ ๋ด์ผ ํ ๋ถ๋ถ์ top ๋ณ์ ๊ฐ์ ๋ณํ์ด๋ค.
push ํจ์์์๋ ์ ์ ์ฆ๊ฐ๋๊ณ ์๊ณ , pop ์์๋ ํ์ ๊ฐ์๋๊ณ ์๋ค.
์๋ฃ๋ฅผ ๋ฃ๊ธฐ ์ํด์ ๋ฏธ๋ฆฌ ์์น๊ฐ ์ ํด์ ธ ์์ด์ผ ํ๊ณ , ๋ฐ๋๋ก ๋บ ๋์๋ ์๋ฃ๊ฐ ๋์จ ํ ์ต์์ ์์น๊ฐ ๋ค์ ๊ณ์ฐ๋์ด์ผ ํ๋ค.
์ฐ๋ฆฌ ์ผ์์์ ์๋ก์ด ์ง์ผ๋ก ์ด์ฌ๊ฐ๋ค๊ณ ์๊ฐํ๋ฉด ์ดํดํ๊ธฐ ์ฌ์ธ ๊ฒ์ด๋ค. (๋จผ์ ์ง์ ๊ตฌํ ๋ค ๋ค์ด๊ฐ๊ณ , ๋์ฌ ๋์๋ ์ ๋ฆฌ ๋จผ์ ํ ํ ๋ฐฉ์ ๋บ๋ค)
์๋ฃ๋ฅผ ๋ฃ๊ณ ๋นผ๋ ๊ธฐ๋ฅ์ ๊ตฌํํ์ผ๋, ์ด๋ฒ์๋ ๋๋จธ์ง ๋ ๊ธฐ๋ฅ(peek, isEmpty)์ ๊ตฌํํด๋ณด์.
int peek(void):
int isEmpty(void);
int peek(void)
{
if (isEmpty())
{
printf("์คํ์ด ๋น์ด์์ด์");
return 0;
}
return stack[top];
}
int isEmpty(void)
{
return top == -1 ? 1 : 0;
}
peek์ ํ์ฌ ์คํ ์ต์๋จ์ ์ด๋ค ๊ฐ์ด ์๋์ง ํ์ธํ๋ ๊ธฐ๋ฅ์ ์ ๊ณตํ๋ค. ์คํ์ด ๋น์ด์๋์ง ํ์ธํ๊ณ , ๋น์ด์์ง ์์ ๊ฒฝ์ฐ stack[top] ์์น์ ์๋ ๊ฐ์ ์ ๋ฌํด์ฃผ๊ธฐ๋ง ํ๋ฉด ๋๋ค.
isEmpty๋ ์คํ์ด ๋น์ด์๋์ง ํ์ธํ๋ ๊ธฐ๋ฅ์ ์ ๊ณตํ๋ค.
์ฐ๋ฆฌ๋ top ๊ฐ์ด -1 ์ผ ๋ ์คํ์ด ๋น์ด์๋ค๊ณ ํ๋จํ๊ธฐ๋ก ํ์ผ๋ ์ด์ ๋ง๊ฒ ์กฐ๊ฑด์ ์ถ๊ฐํ๋ค.
-1์ธ ๊ฒฝ์ฐ 1(์ฐธ)์ ๋ฐํํ๊ณ , -1์ด ์๋ ๊ฒฝ์ฐ 0(๊ฑฐ์ง)์ ๋ฐํํ๋๋ก ํ๋ค.
์ด๋ ๊ฒ ์คํ์ ๊ธฐ๋ณธ ๊ธฐ๋ฅ์ ๋ชจ๋ ๊ตฌํํด๋ณด์๋ค.
์คํ์ ๋ด๊ฒจ์ ธ์๋ ๊ฐ์ ํ์ธํ ์ ์๋๋ก ์๋์ ๊ฐ์ ํจ์๋ฅผ ์ถ๊ฐ๋ก ๊ตฌํํ๊ณ , ์ง์ ์คํ์ ์ฌ์ฉํด๋ณด๋ฉฐ ๋์ํ๋ ๋ชจ์ต์ ํ์ธํด๋ณด์.
void printStack(void);
// ์คํ ๊ฐ ํ์ธ์ ์ํ ํจ์
void printStack(void) {
if (isEmpty())
{
printf("[]\n");
return;
}
printf("[ ");
for (int i = 0; i < STACK_SIZE; i++)
{
if (i <= top)
{
printf("%d ", stack[i]);
}
else
{
printf("- ");
}
}
printf("]\n");
}
#include <stdio.h>
#define STACK_SIZE 10
int top = -1;
int stack[STACK_SIZE];
void push(int);
int pop(void);
int peek(void);
int isEmpty(void);
void printStack(void);
void push(int data)
{
// ๋ฐฐ์ด ์ธ๋ฑ์ค๋ 0๋ถํฐ ์์์ด๋ฏ๋ก, STACK_SIZE - 1
if (top >= STACK_SIZE - 1)
{
printf("๊ฝ ์ฐผ๋ค!");
return;
}
stack[++top] = data;
}
int pop(void)
{
if (isEmpty())
{
printf("ํ
๋น์ด์๋ค");
return 0;
}
return stack[top--];
}
int peek(void)
{
if (isEmpty())
{
printf("์คํ์ด ๋น์ด์์ด์");
return 0;
}
return stack[top];
}
int isEmpty(void)
{
return top == -1 ? 1 : 0;
}
// ์คํ ๊ฐ ํ์ธ์ ์ํ ํจ์
void printStack(void) {
if (isEmpty())
{
printf("[]\n");
return;
}
printf("[ ");
for (int i = 0; i < STACK_SIZE; i++)
{
if (i <= top)
{
printf("%d ", stack[i]);
}
else
{
printf("- ");
}
}
printf("]\n");
}
int main(void)
{
push(4);
push(-102);
push(23);
push(9);
push(10);
printStack();
int popValue = pop();
printf("pop: %d\n", popValue);
int peekValue = peek();
printf("peek: %d\n", peekValue);
pop();
pop();
printStack();
return 0;
}
/*
Result
[ 4 -102 23 9 10 - - - - - ]
pop: 10
peek: 9
[ 4 -102 - - - - - - - - ]
*/
๋ฉ์ธ ํจ์๋ฅผ ์ดํด๋ณด๋ฉด ์คํ์ 4, -102, 23, 9, 10 ๊ฐ์ ๋ฃ์ ํ ์คํ ๊ฐ์ ์ถ๋ ฅํ๋ ์ฐจ๋ก๋๋ก ๊ฐ์ด ์คํ์ ๋ค์ด๊ฐ ์๋ ๊ฒ์ ๋ณผ ์ ์๋ค.
์ดํ ๊ฐ์ ๊บผ๋ธ ํ ํด๋น ๊ฐ์ ์ถ๋ ฅํด๋ณด๊ณ ์๋ค. ๊ฐ์ฅ ๋ง์ง๋ง์ push ํ ๊ฐ์ 10์ด๊ธฐ ๋๋ฌธ์ ํด๋น ๊ฐ์ด ๋จผ์ ๊บผ๋ด์ก๋ค. (ํ์ ์ ์ถ)
๊ฐ์ด ๊บผ๋ด์ง ์ํ์์ ๊ฐ์ฅ ์์ ์๋ ๊ฐ์ ์ถ๋ ฅ(peek)ํด๋ณด๋ฉด ์ด์ ์ ๋ฃ์๋ ๊ฐ์ธ 9๋ฅผ ํ์ธํ ์ ์๋ค.
๋ง์ง๋ง์ผ๋ก ๊ฐ์ 2๊ฐ ๋ ์คํ์์ ๊บผ๋ธ ๋ค ์คํ ๋ด๋ถ๋ฅผ ๋ณด๋ฉด ๋๋จธ์ง ๋ ๊ฐ์ ๊ฐ์ ํ์ธํ ์ ์๋ค.
์ง๊ธ๊น์ง ์คํ์ ๋ํด ์์๋ณด์๋ค.
์คํ ์๋ฃ๊ตฌ์กฐ๋ ์ฌ๊ท ์๊ณ ๋ฆฌ์ฆ์์ ๋๋ฆฌ ์ฌ์ฉํ๊ธฐ๋ ํ๊ณ , ๋ช๋ช ํ๋ก๊ทธ๋๋ฐ ์ธ์ด์ ๋์์ ์ดํด๋ณด๋ฉด ์ฝ ์คํ(Call stack)์ด๋ผ๋ ๊ฐ๋ ์ด ์กด์ฌํ๊ธฐ๋ ํ๋ค.
์คํ์ด๋ผ๋ ๊ฐ๋ ์ ์ ์์งํ๋๋ก ํ์.