스택은 말그대로 데이터(자료)가 쌓이는 것이다.
쌓아서 자료들을 정리 할 때 특성들이 동일하게 적용된다.
쌓여있는 자료들을 생각하면 자료를 꺼낼 때 가장 위에 있는 자료부터 순서대로 꺼내게 된다.
실생활에서 물건을 정리한다고 생각하지 말고 컴퓨터가 자료를 쌓아서 컴퓨터만의 규칙대로 자료를 처리한다고 생각하면서 이해하면 된다.
용어로 LIFO(Last In First Out) 방식이라고 하는데 참고만 해두자.
Stack을 만들어 보자. (C언어로 예를 들겠음.)
우선 자료를 저장할 공간이 필요할 것이다.
공간을 만들자.
#include <stdio.h>
#define MAX_STACK_SIZE 20
int stack[MAX_STACK_SIZE];MAX_STACK_SIZE를 20으로 정의해주고
int형으로 MAX_STACK_SIZE의 stack 배열을 만들어주었다.
공간을 만들었으니 이제 컴퓨터가 여기에 자료를 쌓아 올릴 수 있도록 틀(규칙)을 만들어 주면 될 것이다.
우선 공간의 바닥부터 위로 한 층씩 자료가 쌓여야 하므로 처음 0번째 칸에서 최대 칸까지 자료를 넣을 때마다 한 층씩 쌓여나가게끔 만들어준다.
여기선 현재 stack의 위치(층)에 대한 정보를 top이라는 변수에 넣어 줄 것이다.
top = -1; //-1로 현재 위치를 지정한 이유는 다음에 나올 코드를 보면 알 수 있다.stack의 위치 정보를 담을 변수 top을 만들어줬으니 이제 자료를 넣거나 뺄 때마다 top 변수를 한 층씩 바꿔주기만 하면 된다. 그러면 순서대로 층층이 자료가 쌓이고 빠지게 된다.
void push(int v)
if(top>=MAX_STACK_SIZE-1)
printf("오버플로우 방지"); //오버플로우 방지. 교재들에서는 IsFull 등의 함수로도 자주 처리함.
else
stack[++top]=value; //처음 top위치를 -1로 해서 배열의 순서 번호 0번부터 메모리 손해가 없게된다.
```'```
int pop()
if(top<0)
printf("언더플로우 방지"); //언더플로우 방지. 교재들에서는 IsEmpty 등의 함수로도 자주 처리함.
else
return stack[top--];이제 Stack을 완성하였다. main에서 pop으로 자료를 반환(빼고)하고 push로 자료를 넣을 수 있는 구조가 되었다.
이것만으로도 웬만한 프로그램 다 구현할 수 있지만 Stack에 엄청나게 많은 자료를 저장해야하는 동시에 적은 자료도 저장해야하는 경우를 생각하면 위의 배열을 통한 Stack은 굉장히 비효율적이다.
1000000000가지 경우의 데이터를 Stack에 저장해야 하는 동시에 몇 개 안되는 데이터도 저장해둘 필요가 있으면 1000000000가지 배열을 만들어두고 2, 3가지의 데이터만 넣고 활용하게 되면 나머지 공간은 전부 무의미하게 소모된다.
그렇기에 우리가 특정한 공간 만큼 지정하지 못하는 양의 데이터를 저장하는 Stack이라면 좀 더 다른 아이디어가 필요하다.
고맙게도 이런 아이디어를 이미 다른 사람들이 연구해서 해결방안을 만들어 놓았다.
바로 연결 리스트를 활용하는 것이다.
연결 리스트는 각 값들이 주소와 다음에 올 값의 주소를 가지고 있기에 매번 값을 Stack에 넣고 뺄 때 Stack의 크기도 함께 변화된다. 앞서 설명한 배열을 이용한 Stack과 다르게 연결 리스트의 값들 하나하나가 독립적으로 존재하며 연결되기 때문이다.
이제 연결리스트를 이용해 Stack을 만들어보자.
우선 연결리스트를 만들자.
typedef struct stack {
int data;
struct stack* link;
}stack;해당 코드에 대한 설명은 생략해도 c언어를 안다면 이해할 것이다.
이제 위치값을 저장할 연결리스트 top을 만든다.
stack* top;이제 데이터를 넣고 빼는 함수를 구현하자.
void push(int v){
stack* newnode = (stack *)malloc(sizeof(stack)) // malloc =memory alloc 코드 내용 그대로 메모리 할당 sizeof stack만큼. (stack *)으로 형변환해서 stack* newnode에 값 저장.
newnode->data = v;
newnode->link = top;
top = newnode; //데이터를 push하면 가장 윗쪽에 데이터가 쌓여야하므로 stack에서의 위치를 담는 변수 top에 newnode 주소를 저장. 이해가 잘 안되시면 위 코드 내용을 머릿속으로 반복해보세요. 다음에 생성될 노드에 top 위치값을 넣고 현재 stack 꼭대기 위치 top을 재설정해주고 하면서 연결되는 흐름이 보일 겁니다.
}//node는 연결리스트에서 각 하나하나의 형태를 말합니다. (주소, 값, 다음 연결될 주소)int pop(){
if(top==NULL){ //비어있음 방지.
printf("Empty Stack!");
}
else {
stack* temp = top; //top위치의 노드를 없애야하므로 temp에 top을 저장하고
int data = temp->data; //top(temp)의 데이터를 return해야 하므로 temp->data값을 data를 int 형으로 선언해서 저장하고
top = temp->link;//temp(top)이 가르키는 다음 주소 값을 top에 저장해주고
free(temp);//노드 temp를 free해준다. 그러면 top은 한칸 위로 이동하고 이전 칸은 temp로 주소와 데이터가 옮겨지고 free되어 삭제된다.
return data;//마지막으로 data return.
}
연결 리스트를 이용한 Stack 까지 완성!
그럼 이것들은 어디에서 활용되고 있는가?
1. 시스템 스택.
프로그램에서 호출과 복귀의 수행 순서를 저장하고 관리한다.
ex) 함수 수행에 필요한 다양한 변수들을 저장하고 복귀 주소도 저장하여 저장된 정보를 시스템 스택에 삽입한다. 프로그램이 순서대로 실행되며 함수호출과 복귀에 필요한 정보가 push되고 top에 있는 스택을 pop하여 정보를 확인하고 복귀, 작업 전환한다. 이것이 main 함수(전체 프로그램)까지 수행되면 공백 스택이 되어 프로그램이 종료된다.
-
수식의 괄호 검사
1) 왼쪽 괄호를 만나면 push
2) 오른쪽 괄호를 만나면 pop해서 마지막으로 저장된 괄호와 비교. ex {( )pop 비교 같은 종류 ok ]pop 비교 같은 종류 no.
3) 검사가 끝나고 공백 스택인지 체크. 그리고 종료. -
전위 표시, 중위 표시, 후위 표시 변환
ex. 중위 표시를 후위 표시법으로.
1) '('형태의 괄호를 만나면 무시하고 다음 문자 확인.
2) 피연산자를 만나면 출력.
3) 연산자를 만나면 스택에 삽입.
4) ')'형태의 괄호를 만나면 스택을 pop하여 출력.
5) 공백이 될 때 까지 pop하여 출력.
ex. ((A/B)+(C/D)) // , = 무시 . = 출력 ! = push ? = pop
-> , , .!. ? !, . ! . ?? -> AB/CD/+ -
후위 표기법 연산
1) 피연산자를 스택에 push
2) 연산자를 만나면 필요한 만큼 피연산자를 스택에서 pop, 연산 결과를 스택에 push.
3) 수식이 끝나면 스택을 pop하여 출력.
ex. AB/CD/+ //! = push ? = pop
. . . ! !??! !????
. . . . . . . . . !(연산 결과를 push) 그리고 pop
제가 공부한 내용 정리한다고 적은 글입니다.
혹시나 이 글을 공부에 참고하시는 분들 중에 추가 설명이 필요하신 분이 계신다면 댓글 남겨주시면 적극적으로 답변해드리겠습니다.
