Kim Ji Soo

I am an amazing person.

스택

식판을 쌓듯이 자료를 차곡차곡 쌓아 올린 형태 순서리스트 (=pushdown 리스트)의 특별한 자료구조를 말함

  • 후입선출(LIFO : Last-In-First-Out) 프로토콜을 구현하는 자료구조
  • 스택의 주소를 알려주는 포인터
    • top의 위치에서만 원소를 삽입하므로 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓임
  • 스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능함
  • 스택의 밑(bottom)에서부터 스택의 크기까지의 범위를 가짐


스택의 삽입

스택 S = (a0, … , an-1)

  • a0 : bottom 원소, an-1 : top 원소, ai : 스택원소 (0 < i < n , i+1 번째 원소)

삽입은 리스트의 마지막에서 이루어짐 - push()

삽입 알고리즘

push(s, e){
    if(top == SIZE) stack-overflow;
    top = top+1;
    stack[top] = e;
}

스택의 삭제

삭제도 리스트의 마지막에서 이루어짐 - pop()

삭제 알고리즘

pop(s){
    if(top == 0) stack-underflow;
    e = stack[top];
    top = top-1;
    return e;
}


스택의 순차 표현

1차원 배열을 이용한 스택의 구현

스택을 표현하는 가장 간단한 방법임

  • n = 스택에 저장할 수 있는 최대 원소 수
  • top = 스택의 최상위 원소
  • 공백상태 => top = -1(초기값), 포화 상태 => top = n-1

스택도 배열에 의해 저장되므로 배열의 속성을 가짐

  • 동일한 자료형만 저장
  • 배열의 크기에 의해 원소 개수의 제한을 받음

스택의 1차원 배열 표현의 장단점

  • 장점 - 순차 자료구조인 1차원 배열을 사용하여 쉽게 구현할 수 있음
  • 단점 - 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경이 어려움


스택 연산의 구현

1차원 배열의 크기(stack[8])에서 오버플로우와 언더플로우를 검사하는 프로그램

#include<stdio.h>

int MAXSIZE = 8;
int stack[8];
int top = -1;

int isempty(){
    if(top == -1)
        return 1;
    else
        return 0;
}

int isfull(){
    if(top == MAXSIZE)
        return 1;
    else
        return 0;
}

int peek(){
    return stack[top];
}

int push(int data){
    if(!isfull()){
        top = top + 1;
        stack[top] = data;
    } else{
        printf("Could not insert data, Stack is full.\n");
    }
}

int pop(){
    int data;
    if(!isempty()){
        data = stack[top];
        top = top - 1;
        return data;
    } else{
        printf("Could not retrieve data, Stack is empty.\n");
    }
}

int main(){
    push(3);
    push(5);
    push(9);
    push(1);
    push(12);
    push(15);

    printf("Element at top of the stack: %d\n", peek());
    printf("Elements:\n");

    while(!isempty()){
        int data = pop();
        printf("%d\n", data);
    }

    printf("Stack full: %s\n", isfull()?"true":"false");
    printf("Stack empty: %s\n", isempty()?"true":"false");
    return 0;
}

실행 결과

Element at top of the stack: 15
Elements:
15
12
1
9
5
3
Stack full: false
Stack empty: true



스택의 응용 : 시스템 스택

시스템 스택(system stack)/실행시간 스택(runtime stack)

기억 공간의 데이터들을 효율적으로 관리하기 위한 데이터 참조 방식의 자료구조를 말함

  • 프로그램 실행 시 시스템이 사용하는 대표적인 스택(기억공간)
  • 실행 스택(excution stack), 제어 스택(control stack), 런 타임 스택(run-time) 스택, 기계 스택(machine stack)이라고도 함

함수간의 호출과 복귀에 따른 실행순서관리를 위한 제어

  • 함수 호출 시 시스템은 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 활성화 레코드(activation record) 또는 스택 프레임(stack frame)을 만들어 스택에 삽입



스택의 응용 : 문자열 역순/괄호검사

문자열 역순 출력 방법 및 예

  1. 문자열을 읽어 문자열 끝까지 차례대로 스택에 삽입(push)
  2. 스택이 비워질(empty) 때까지 문자들을 삭제(pop)

문자열 = “computer science”를 역순으로 출력하는 프로그램

#include<stdio.h>
#include<string.h>
#define MAX 100 // 최대 문자열의 길이

int top = -1; // 스택 변수
int item;
char stack_string[MAX];
void pushChar(char item);
char popChar(void);
int isEmpty(void);
int isFull(void);

int main(){
    char str[MAX];
    int i;
    printf("Input a string:");
    scanf("%[^\n]s",str); // 문자열 입력

    for(i=0; i<strlen(str); i++)
        pushChar(str[i]);

    for(i=0; i<strlen(str); i++)
        str[i] = popChar();

    printf("Reversed String is: %s\n",str);
    return 0;
}

void pushChar(char item){
    if(isFull()){
        printf("\nStack is FULL!!!\n");
        return;
    }

    top = top+1;
    stack_string[top] = item;
}

char popChar(){
    if(isEmpty()){
        printf("\nStack is EMPTY!!!\n");
        return 0;
    }
    
    item = stack_string[top];
    top = top-1;
    return item;
}

int isEmpty(){
    if(top == -1)
        return 1;
    else
        return 0;
}

int isFull(){
    if(top == MAX-1)
        return 1;
    else
        return 0;
}

실행 결과

Input a string: computer science
Reversed String is: ecneics retupmoc


괄호 검사

괄호( (, ), {, }, [ ,] )가 서로 대응하며 적절하게 내포되었는지 파악하는 검사를 말함 - 컴파일러에서 구문 체크 시 활용

수식에 포함되어있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 LIFO구조로 구성되어 있음

괄호 검사 방법

  1. 입력 문자열(수식)에서 현재의 문자가 시작 괄호이면 스택에 삽입함(push)
  2. 현재의 문자가 닫는 괄호이면 스택에서 삭제(pop)
  3. 입력 문자열의 마지막 문자까지 읽었을 때 스택에 시작 괄호가 남아 있으면 균형을 이루지 못함, 즉 괄호가 닫히지 않음

괄호 검사하는 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20

struct stack{
    char stk[MAX];
    int top;
}s;

void push(char item){
    if(s.top == (MAX - 1))
        printf("Stack is Full\n");
    else{
        s.top = s.top + 1; //포인터를 1 증가 후 괄호를 삽입
        s.stk[s.top] = item;
    }
}

void pop(){
    if(s.top == -1){
        printf("Stack is Empty\n");
    }
    else{
        s.top = s.top-1; // 괄호를 삭제 후 포인터 감소
    }
}

int main(){
    char exp[MAX];
    int i = 0;
    s.top = -1;
    printf("\n입력 식:");
    scanf("%s", exp);

    for(i=0; i<strlen(exp); i++){
        if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{'){
            push(exp[i]); // 시작 괄호를 스택에 삽입
            continue;
        }
        else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}'){
            if(exp[i] == ')'){ // 닫는 괄호이면 스택에서 삭제
                if(s.stk[s.top] == '('){
                    pop();
                }
                else{
                    printf("\n괄호의 균형을 이루지 못한 수식\n");
                    break;
                }
            }
            if(exp[i] == ']'){
                if(s.stk[s.top] == '['){
                    pop(); 
                }
                else{
                printf("\nUNBALANCED EXPRESSION\n");
                break;
                }
            }
            if(exp[i] == '}'){
                if(s.stk[s.top] == '{'){
                    pop(); 
                }
                else{
                    printf("\nUNBALANCED EXPRESSION\n");
                break;
                }
            }
        }
    }
    
    if(s.top == -1){ //stack이 empty이면 balanced함
        printf("\n입력식의 괄호 개수가 BALANCED이다.\n");
    }
}

출력결과

입력 식:{(a+b)/[{(c-d)/2}*2]}

입력식의 괄호 개수가 BALANCED이다.

You may also enjoy