[DS] Stack (스택)

1. # 스택

- stack: 선형 리스트의 특별한 형태로, 책 또는 접시 같은 것들을 쌓아 둔 것을 의미

- 후입 선출(LIFO: Last-In, First-Out) 구조

- 함수 호출, 문법 검사, 연산식 평가 등에 활용

- 다음과 같이 원소들의 리스트로 정의 가능

   S = [a0, a1, ...., an-1]

- push: 원소 추가 / pop: 원소 삭제

- ex) 스택에 원소 a, b, c, d, e 삽입 및 삭제

 

 

 

2. # 스택 예제

(1) Balanced Parentheses

- 괄호의 짝이 맞는지 확인하는 예제

 

[코드]

 

      

      

      

    
    

      <c++ />
    
// c++로 구현한 check_balance 함수
void check_balance(char* p) {
	struct Stack stack;
	create(stack, LINESIZE);
	istrstream c(p);
	char s = c.get();
	int i = 0;
	while (i<strlen(p) + 1) {
		cout << s;
		if (s == '('||s=='{'||s=='[')
			push(stack, s);
		else if ((s == ')'&&pop(stack)!='(')|| (s == '}'&&pop(stack) != '{')|| (s == ']'&&pop(stack) != '[')){
				cout << ": MISMATCHING!!\n"; return;
		}
		s = c.get();
		i++;
	}
	if (isempty(stack))
		cout << ": BALANCED!!\n";
	else
		cout << ": MISMATCHING!!\n";
}

 

[실행결과]

 

 

 

(2) Decimal to Binary

 

 

- 10진법을 2진법으로 변환하는 코드

- 123(10) => 1111011(2)

- S = [1, 1, 0, 1, 1, 1, 1]

 

 

 

 

 

 

 

 

 

[코드]

      

      

      

    
    

      <c++ />
    
#include<stdio.h>
# define MAX 100

int stack[MAX];
int top = 0;

int pop();
void push(int a);

int main() {
	int input=0;

	printf("이진수로 변환할 숫자를 입력하세요: "); scanf("%d", &input);
	

	do {
		push(input % 2);
		input /= 2;
	} while (input); // input이 0이되면 계산이 끝나야 함

	while(top) { // top이 0이 되면 stack에 남아있는 원소가 없음
		printf("%d",pop());
	}
	printf("\n");
}

int pop() {
	if (top < 0) {
		printf("stack empty");
		return 111;
	}
	return stack[--top];
}

void push(int a) {
	if (top >= MAX - 1) {
		printf("stack_full\n");
	}
	else stack[top++] = a;
}

 

[실행결과]

 

(3) Function call

- 함수가 실행 중에 다른 함수가 호출되었을 때, 실행 중이던 함수의 context 정보를 활성레코드에 저장

- context: 지역 변수, 다시 시작해야하는 명령어의 주소, 이전 stack frame의 포인터

- 활성 레코드(= 스택 프레임)

  > 함수의 환경 정보를 담고 있는 구조체

  > 실행되는 함수마다 1개씩 생성되어 스택에 저장됨

- 시스템 스택: 함수 호출을 관리하기 위해 사용하는 스택

 

      

      

      

    
    

      <c++ />
    
A()                          // SS = [A]
{
  B()                        // SS = [A, B]
  {
    C(){                     // SS = [A, B, C]
        ...
        }                    // SS = [A, B] → C() 함수 호출이 끝나서 pop
    D(){                     // SS = [A, B, D]
        ...
        }                    // SS = [A, B] → D() 함수 호출이 끝나서 pop
  }                          // SS = [A] → B() 함수 호출이 끝나서 pop
}                            // SS = [] → A() 함수 호출이 끝나서 pop

 

 

3. # 스택 구현

- top 포인터

  > 스택에 가장 나중에 삽입된 원소를 가리키며, 그 위치에 해당하는 배열 인덱스 값 가짐

  > 빈 스택(empty stack) 상태에서 top 포인터는 -1 값을 가짐

  > 주소값을 갖는 변수 자료형인 포인터와 동일시 X

  > empty 스택이 아니라는 가정하에 0 ~ STACK_SIZE -1(upper bound)까지의 값을 가짐

- push()

  > 스택이 가득 찬 full stack 상태: top >= STACK_SIZE -1 (upper bound)

  > full stack이 아닐 경우: top을 증가시킨 후 해당 인덱스에 원소를 저장

      

      

      

    
    

      <c++ />
    
void push(int item){
  if(top >= STACKSIZE - 1){  // stack full
    printf("stack full");
    return;  //  "stack full"을 출력한 후 바로 종료
  }
  stack[++top] = item;
  print_stack();
}

 

 

- pop()

> empty stack: top <= -1, -999 반환

> empty stack이 아닐 경우: stack 포인터가 가리키는 원소 반환 후 top 감소

      

      

      

    
    

      <c++ />
    
int pop(){
  if(top < 0){
    printf("empty stack");  // empty stack
    return -999;
  }
  return stack[top--];
}

 

 

- 스택 구현

[코드]

      

      

      

    
    

      <c++ />
    
#include <stdio.h>
#define STACK_SIZE 100
int stack[STACK_SIZE];
int top = -1;

void push(int item);
int pop();
void print_stack();

int main(){
  push(3);
  push(4);
  push(5);
  pop();
  print_stack();
  pop();
  print_stack();
  pop();
  print_stack;
}

void print_stack(){
  for(int i = 0; i <= top; i++)
    printf("%d ", i);
  printf("\n");
}

void push(int item){
  if(top >= STACK_SIZE - 1){
    printf("stack full");
    return;
  }
  stack[++top] = item;
  print_stack();
}

int pop(){
  if(top < 0){
    printf("empty stack");
    return -999;
  }
  return stack[top--];
}

 

[실행결과]