[Data Structure] Stack(스택)

2023-01-11 3 분 소요

스택은 Last-in first-out(LIFO)의 특징을 가진 선형 리스트이다. 알고리즘적으로는 괄호 검증, DFS, 후위표기식 변환 및 계산에 주로 사용되며, 브라우저의 히스토리 기능과 함수 호출에서 이 구조를 발견할 수 있다.

추상자료형 스택

유한 선형 리스트
메서드는 create(size), is_full(s), is_empty(s), peek(s), push(s, item), pop(s)
만약 스택이 모두 찬 상황에서 push(s, item)을 호출할 경우, 오류 발생
만약 스택에 원소가 없는 경우에서 pop(s)를 호출할 경우, 오류 발생
C언어로 구현하는 방식으로는 배열을 이용한 방식과 연결 리스트를 이용한 방식이 있음
필자는 이 챕터에서는 배열을 이용한 방식만을 정리

구현

1차원 배열 및 top을 모두 전역변수로 관리 - 쉽게 사용할 수 있으나 여러 개의 스택 관리하기 힘듬

 #include <stdio.h>
 #include <stdlib.h>

 #define MAX_STACK_SIZE 100
 typedef struct{
   int student_no;
   char name[MAX_STACK_SIZE];
   char address[MAX_STACK_SIZE];
 }element;

 element stack[MAX_STACK_SIZE];
 int top = -1;

 int is_empty(){
   return (top == -1);
 }

 int is_full(){
   return (top >= (MAX_STACK_SIZE-1));
 }

 void push(element item){
   if (is_full()){
     fprintf(stderr, "스택이 가득 찼습니다. 삽입이 안됩니다\n");
     return;
   } else{
     stack[++top] = item;
   }
 }

 element pop(){
   if (is_empty()){
     fprintf(stderr, "스택이 비었습니다.");
     exit(1);
   } else{
     return stack[top--];
   }
 }

 element peek(){
   if (is_empty()){
     fprintf(stderr, "스택이 비었습니다.");
     exit(1);
   } else{
     return stack[top];
   }
 }


 int main(void) {

   printf(is_empty() ? "true\n" : "false\n");
   element pugcute = {
     202020, "pugcute", "andong"
   };
   element pop_text;
   push(pugcute);
   printf("%s\n", peek().name);
   pop_text = pop();
   printf("%d\n", pop_text.student_no);
 }

함수의 매개변수로 stack을 전달하는 경우 - stack 구조체를 만들어 그 안에서 element 배열과 top을 관리, 단 구조체의 포인터를 함수에 전달해야 함(함수 매개변수 전달 방식인 call by value이므로 포인터를 안 쓸 경우, 복사된 데이터만 변화할 뿐 원본 데이터가 변화하지 않음)

 #include <stdio.h>
 #include <stdlib.h>

 #define MAX_STACK_SIZE 100
 typedef struct{
   int student_no;
   char name[MAX_STACK_SIZE];
   char address[MAX_STACK_SIZE];
 }element;

 typedef struct{
   element data[MAX_STACK_SIZE];
   int top;
 } stack;

 void init_stack(stack *s){
   s -> top = -1;
 }

 int is_empty(stack *s){
   return (s -> top == -1);
 }

 int is_full(stack *s){
   return (s -> top >= (MAX_STACK_SIZE-1));
 }

 void push(stack *s, element item){
   if (is_full(s)){
     fprintf(stderr, "스택이 가득 찼습니다. 삽입이 안됩니다\n");
     return;
   } else{
     s->data[++(s->top)] = item;
   }
 }

 element pop(stack *s){
   if (is_empty(s)){
     fprintf(stderr, "스택이 비었습니다.");
     exit(1);
   } else{
     return s->data[(s->top)--];
   }
 }

 element peek(stack *s){
   if (is_empty(s)){
     fprintf(stderr, "스택이 비었습니다.");
     exit(1);
   } else{
     return s->data[s->top];
   }
 }


 int main(void) {
   stack s;
   init_stack(&s);
   printf(is_empty(&s) ? "true\n" : "false\n");
   element pugcute = {
     202020, "pugcute", "andong"
   };
   element pop_text;
   push(&s, pugcute);
   printf("%s\n", peek(&s).name);
   pop_text = pop(&s);
   printf("%d\n", pop_text.student_no);
 }

괄호 검사 알고리즘

while True:
    words = input()
    if words == '.':
        break
    stack = []
    flag = 0
    for word in words:
        if word in ['(', '[']:
            stack.append(word)
        if word in [')', ']']:
            if len(stack) == 0:
                flag = 1
                break
            else:
                tmp = stack.pop()
                if word == ')' and tmp == '(':
                    continue
                if word == ']' and tmp == '[':
                    continue
                else:
                    flag = 1
                    break
    if len(stack) > 0:
        flag = 1

    if flag == 0:
        print('yes')
    else:
        print('no')

( 또는 [는 stack에 바로 저장
) 또는 ]가 등장할 경우, 먼저 stack의 원소가 비었는지를 확인. 오른쪽 괄호가 먼저 등장한 것이므로 위배
) 또는 ]가 등장할 경우, 쌍이 맞는지를 확인. 쌍이 맞지 않으면 위배
만약 문자열을 순회했음에도 불구하고 스택에 원소가 남아있다면, 왼쪽 괄호가 더 많은 것이므로 위배

후위 표기식

프로그래머는 주로 연산자가 피연산자 사이에 있는 중위 표기식을 사용하나, 컴퓨터는 연산자가 피연산자 뒤에 위치하는 후위 표기식을 사용한다. 중위표기식을 입력하면 컴파일러는 후위표기식으로 변환하여 계산한다.

후위표기식의 계산

피연산자는 스택에 담는다.
연산자가 등장할 경우에는 스택에서 pop()을 두 번하여 이를 first, second에 할당한 후, 연산자에 맞게 계산한다.
2의 계산 결과를 다시 스택에 담는다.
입력한 것을 모두 순회할 때 1-3의 과정을 수행한다.

N = int(input())
words = input()
stack = []
dict_alpa = {}
for i in range(N):
    tmp = int(input())
    dict_alpa[chr(65+i)] = tmp
    # 이 식의 숫자를 알파벳으로 주어지므로, 딕셔너리로 관리함

for word in words:
    if word not in ['+', '-', '*', '/']:
        stack.append(dict_alpa[word])
    else:
        first = stack.pop()
        second = stack.pop()
        if word == '+':
            stack.append(first + second)
        elif word == '-':
            stack.append(second - first)
        elif word == '/':
            stack.append(second / first)
        elif word == '*':
            stack.append(first * second)
print(f'{stack[0]:.2f}')

중위 표기식 -> 후위표기식

피연산자는 출력한다.
연산자의 경우, (는 스택에 바로 담는다. )는 스택에 있는 )가 등장할 때까지 pop()을 실행한다.
+, -의 우선순위는 1로, *, /의 우선순위는 2로 설정한다. 만약 스택의 top인 원소의 우선순위가 연산자의 우선순위보다 크거나 같다면, top인 원소의 우선순위가 낮아질 때까지 pop()을 실행한다.
수식 순회가 끝났을 때, 스택에 연산자가 남아 있다면 스택의 원소가 없을 때까지 pop()을 실행한다.

words = input()
stack = []
answer = []
prior = {'(': 0, '+': 1, '-': 1, '*':2, '/' : 2}

for word in words:
    if word not in ['(', ')', '+', '-', '*', '/']:
        answer.append(word)
    else:
        if word == '(':
            stack.append(word)
        elif word == ')':
            tmp = stack.pop()
            while tmp != '(':
                answer.append(tmp)
                tmp = stack.pop()

        else:
            while len(stack) and prior[stack[-1]] >= prior[word]:
                tmp1 = stack.pop()
                answer.append(tmp1)
            stack.append(word)

if len(stack):
    while stack:
        tmp = stack.pop()
        answer.append(tmp)

print(''.join(answer))

Twitter Facebook LinkedIn

pugcute

[Data Structure] Stack(스택)

추상자료형 스택

구현

괄호 검사 알고리즘

후위 표기식

후위표기식의 계산

중위 표기식 -> 후위표기식

공유하기

댓글남기기

참고

[HTML] HTML 정리 - 입력 양식

[NETWORK] OSI 7Layer

[HTML] HTML 정리

[SQL] 코딩테스트 대비용 SQL