[C언어/자료구조] Stack. 스택의 의미와 필수 함수, 응용

여러분 안녕하세요. 

이번글에서는 Stack은 무엇인가? stack에 쓰이는 함수를 

소개하겠습니다.

(stack을 활용한 표기식 변환 방법 아래 링크 참고하세요)

2021.09.16 - [자료구조] - [자료구조] 중위표기식 < - >후위표기식 변환 방법(stack의 응용)

1. Stack이란 무엇인가?

(같은 자료형)데이터를 차곡 차곡 쌓아올린 형태를 Stack이라고 합니다.

ex) 연탄 아궁이에 연탄을 넣는것과 꺼내는 방법과 같은 개념입니다.

연탄을 넣을 입구는 하나 이고, 가장 처음 넣은 연탄은 가장 마지막에 뺄 수 있습니다.

 

'top'으로 정한 곳에서만 삽입(push), 삭제(pop)가 가능합니다.

그렇게 정의되어있습니다!!!!!(특징입니다 stack의 특징)

 

 위의 원리에 따라 삽입한 순서대로, 그 데이터가 아래에서 위로 쌓이게 되고,

가장 마지막에 삽입push된 (Last In)데이터가 가장 먼저 삭제pop(First Out)되는 구조적 특징을 갖고 있습니다.

LIFO 구조 : 후입선출 이라고 합니다.

---

Stack은 주로 배열로 많이 사용됩니다.

#define STACK_SIZE 100

typedef int element;
element stack[STACK_SIZE];

int stack[]이라고 배열을 선언해도 좋지만,

 

"주로 element(원소)에 대해서 삽입과 삭제를 할 것이다"라는 표현을 심어주기 위해서 typedef했습니다.

2.  stack의 대표적인 함수 push , pop, IsEmpty,IsFull

배열에 element를 집어 넣기 위해서는 삽입과 삭제 등 처리과정이 있어야합니다.

이때 삽입하는 과정을 push한다 라고합니다

삭제하는 과정은 pop이라고 합니다.

하지만 이 둘을 사용하기 전에 몇가지 숙지해야할 것이 있습니다.

 

바로 "top"의 개념입니다.

top이란 쌓여있는 stack의 배열 중에서 가장 최근에 삽입된 원소,

Stack에서 가장 위에 있는 원소를 뜻합니다.

새로운 element가 stack에 push 되면 top또한 즉시 갱신되어 

최근에 삽입된 element를 지목합니다.

 

 

stack에 element a, element b, element c가 순서대로 

삽입 처리 되어있습니다.

이때의 top은 가장 위에있는 데이터를 가리키게 됩니다.

 

 

 

 

 

 

 

 

 

새로운 데이터 element d를 push하게 된다면,

더이성 element c는 가장 최근에 삽입된 원소가 아니므로 

top의 값 또한 증가되어 Last In(가장 최근에 삽입된)

element d를 지목할 것입니다.

 

 

 

 

 

 

 

push와 pop 연산을 하기전에 반드시 알아야 할 함수가 있습니다.

Stack에 element가 꽉 찼는데 또 원소를 추가한다던가,,

Stack에 원소가 텅 비었는데 원소를 pop한다던가,, 의

무의미한 작업을 최소화 하기 위해

 

Stack의 상태가 비어있는 상태인가?

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

Stack의 상태가 Full한 상태인가?

int isFull() {
	if (top == STACK_SIZE-1) // index==0에 첫번째 값이 저장될 경우 top==0이므로, STACK_SIZE-1이 MAX Index이다. 
		return 1;
	else
		return 0;
}

이 두 함수가 필요합니다. 

그래야만 stack에 삽입 삭제를 할 때 

원활한 작업을 수행할 수 있습니다.

 

삽입 연산(push)

void push(element item) {
	if (isFull()) {
		printf("\n\n Stack is Full");
		return ;
	}
	else stack[++top] == item; //전역변수로 선언된 변수 top이기에 stack에 값을 입력할 때마다 top을 1 증가시켜 그 값을 스택에 저장한다.
}

삭제 연산(pop)

element pop() {
	if (isEmpty()) {
		printf("\n\n Stack is Empty!!");
		return 0;
	}
	else return stack[top--]; //현재 맨 꼭대기에 저장된 값을 반환하고 top의 위치를 반환해야한다.
}

추가적으로  top에 대한 원소가 무엇인지를 알려주는 peek함수

element peek() {
	if (isEmpty()) {
		printf("\n\n Stack is Empty");
		exit(1);
	}
	else return stack[top];
}

stack에 저장된 element를 출력하는 printStack함수

void printStack() { //stack에 저장된 값을 출력합니다.
	int i;
	printf("\n STACK[");
	for (int i = 0; i <= top; i++)
		printf("%d", stack[i]);
	printf("]");
}

위의 함수들을 알게 된다면 Stack을 사용한 자료의 저장은 쉽게 진행할 수 있습니다.

 

3.Stack의 활용

char[50]="~~~";

1. 문자열의 역순을 쉽게 출려할 수 있습니다. stack에 문자열을 차례대로 push 후

다시 그 문자들을 pop하며 출력하면 되는 것입니다.

 

2.프로그램에서 실행되는 함수는 LIFO구조를 사용합니다.

예를들어 main함수에서 특정한 함수 Func() 가 실행됬을 경우, stack에는 main->  Func()

가 저장되고, 이후 Func()함수가 종료되었을 때 Func를 pop연산 후 다시 main함수를 마저 진행시킵니다.

 

3. 컴퓨터의 연산 처리과정

사람의 경우에는 쉽게 괄호가 어디서부터 어디까지인지,

무슨 괄호부터 연산해야하는지

무엇이 연산자인지, 괄호인지, 피연산자인지를 한눈으로 파악하기 쉽지만

 

우리의 컴퓨터는 그렇지 않습니다...

따라서 컴퓨터는 "후위 표기법"에 따라서 식을 처리합니다.

후위 표기법의 사용은 괄호의 우선순위에 따라 처리하지 않고 

그냥 후위표기식으로 정리 후 ,

왼쪽에서 오른쪽으로 표기된 순서대로 처리를 합니다.

4. 중위 표기식->후위 표기식 변환 방법

2021.09.16 - [자료구조] - [자료구조] 중위표기식 < - >후위표기식 변환 방법(stack의 응용)