π‘ μ μ
μ€νμ νμͺ½μΌλ‘λ§ λ°μ΄ν°λ₯Ό λ£κ³ λΊ μ μλ ννμ λ°μ΄ν° ꡬ쑰λ‘, νμ
μ μΆ(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)μ΄λΌλ κ°λ μ΄ μ‘΄μ¬νκΈ°λ νλ€.
μ€νμ΄λΌλ κ°λ μ μ μμ§νλλ‘ νμ.