스택

스택이란 데이터를 차곡 차곡 쌓아 올린 데이터 구조이다 한쪽 방향으로 입력과 출력이된다 스택과 다른 데이터 구조는 큐가 있다

스택

스택에 저장된 원소는 top으로 지정된 곳에서만 접근이 가능하다 top으로 정한 위치에서만 원소를 삽입하므로 먼저 입력한 원소는 점점 아래에 저장된다 마지막에 입력한 원소는 가장 먼저 삭제된다 (Last-In-First-Out, LIFO)

 

 

스택의 연산

• push: 원소 삽입 연산

• pop: 원소 삭제 연산

 

배열로 스택 구현

#include<stdio.h>
#define MAX 20

int stack[MAX];
int top = -1;

void push (int item){
    stack[++top] = item;
}

int pop(){
    return stack[top--]; //top의 마지막 원소 반환후 top값 -1
}

int peek(){
    return stack[top]; //stack의 top요소를 확인한다
}

void printStack(){
    int i ;
    printf("\nStack [");
    for(i=0;i<=top;i++){
        printf(" %d", stack[i]);
    }
    printf("]");
}

void main() {
    int item;
    printStack();
    push(1); printStack();
    push(4); printStack();
    push(3); printStack();
    push(10); printStack();

    item = peek(); printStack();
    printf("peek = %d\n", item);

    item = pop(); printStack();
    printf("pop = %d\n", item);
}

물리적으로 크기가 고정된 배열을 사용해서 스택의 크기변경이 어렵다

 

 

연결리스트 스택 구현

#include <stdio.h>
#include <stdlib.h>
typedef struct _stackNode
{
    int data;
    struct stackNode *link;
} stackNode;

stackNode *top;

void push(int item){
    stackNode *temp = (stackNode*)malloc(sizeof(stackNode));
    temp -> data = item;
    temp -> link = top; //삽입 노드를 top 노드에 현재 top위치를 저장 시킨다
    top = temp; // top은 새로 생긴 top을 저장한다
}

int pop(){
    int item;
    stackNode *temp = top;
    
    item = temp -> data;
    top = temp -> link;
    free(temp);
    return item;

}

int peek() {
    return top -> data;
}

void printStack(){
    stackNode *p = top;
    printf("stack = [");
    while (p){
        printf("%d ", p->data);
        p = p -> link;
    }
    printf("] \n");
}
int main () {
    int item;
    push(1); printStack();
    push(5); printStack();
    push(4); printStack();
    push(7); printStack();
    item = peek(); printStack();
    printf("%d peek \n ", item);
    item = pop(); printStack();
    printf("%d pop \n", item);
}

 

 

스택을 이용한 수식의 표기법

전위 표기법 (prefix notation)

연산자를 피연산자 앞에 표기하는 방법 ex) +ab

 

중위 표기법(infix notation)

연산자를 피연산자 가운데 표기 -> 평소 사용하는 방법 ex) a+b

 

후위 표기법(postfix notation)

연산자를 피연산자 뒤에 표기하는 방법 ex) ab+

 

스택을 이용한 표기법 변환 (중위 -> 후위)

1. 왼쪽 괄호는 만나면 무시하고 다음 문자를 읽는다
2. 피연산자를 만나면 출력한다
3. 연산자를 만나면 스택에 삽입한다
4. 오른쪽 괄호를 만나면 스택을 pop하여 출력
5. 수식이 끝나면 스택이 빌때까지 pop하여 출력한다

 

스택을 이용한 후위 표기법 연산

1. 피연산자를 만나면 스택에 push
2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고 스택에 다시 push
3. 수식이 끝나면 마지막으로 스택을 pop하여 출력

 

• 중위 표기 -> 후위 표기법 방법 1

먼저 연산자 우선순위에 따라 괄호를 다시 표현한다

((a*b)-(c/d)) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다

((a*b)(c/d))- => ((ab)*(cd)/)- =>괄호 제거 a b * c d / -

 

• 후위표기법 변환 방법2

모든 연산자에 대해 연산자 우선순위별 괄호가 표현되어 있지 않은 경우에 사용

우선순위	(	)	+	-	*	/	%	eos
isp(stack)	0	19	12	12	13	13	13	0
icp(수식)	20	19	12	12	13	13	13	0

삽입할 연산자 우선순위보다 높거나 같은 경우 연산자를 계속 pop한다

a*b/c => ab/c*

a/b-c+d*e-a*c =>ab/c-de*+ac*-