[자료구조] 스택(Stack)

1. 스택의 개념

• 스택(Stack)의 구조란 쌓인 접시에 가장 먼저 놓은 것은 제일 아래 있는 접시다. 그러나 사용하려고 접시를 집는다면 제일 위에 있는 접시부터 사용하게 된다. 이처럼 들어온 순서와 정반대로 서비스를 받는 것이 스택의 개념이다.

 

2. 스택의 특징

• 데이터의 삽입과 삭제가 한곳에서 이루어지는 방식(Last In First Out = LIFO)
   - Top : 가장 최근에 삽입된 자료
   - Bottom : 스택의 밑바닥
   - 삽입 : Push
   - 삭제 : Pop
• 다중 스택
   - 하나의 기억공간에 여러 개의 스택으로 운영하는 형태로 overflow의 발생방지를 위해 사용
• 스택의 응용
   - 서브루틴호출, 순환 프로그램, 인터럽트 처리, 수식표기, 0-주소, 컴파일러 등

 

3. 스택의 구조

3	C	top
2	B
1	A	bottom

 

스택의 크기는 3이고 A, B, C 순서로 삽입되어 A가 bottom에 있고 C가 top이다.

 

1) 스택의 삽입과 삭제

3		A 삽입 (push A)		B 삽입 (push B)		C 삽입 (push C)	C	C 삭제 (pop C)
2					B		B		B
1			A		A		A		A
	Empty						Full

 

4. 순차 구조를 이용한 스택 구현

• 스택의 크기 : 배열의 크기
• 스택에 저장된 원소의 순서 : 배열 원소의 인덱스
• 인덱스 0번 : 스택의 첫 번째 원소
• 인덱스 n - 1번 : 스택의 n번째 원소
• 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장
• 공백 상태 : top = -1 (초깃값)
• 포화 상태 : top = n - 1

 

1) 장점

• 순차 자료구조인 1차원 배열을 사용하여 쉽게 구현

 

2) 단점

• 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움
• 순차 자료구조의 단점을 그대로 가지고 있음

 

3) C언어 실습

 

#include <stdio.h>
#define MAXSIZE 5	// 스택의 크기 정의
int stack[MAXSIZE];	// 스택의 긴 통
int top;	// 스택의 상단

void init_stack(){	// 스택 초기화
	top = -1;
}

int push(unsigned int val){
	if(top >= MAXSIZE - 1){
		printf("\n Stack Overflow\n\n");
		return -1;
	}
	stack[++top] = val;
	return val;
}

int pop(void){
	if(top < 0){
		printf("\n Stack Underflow\n\n");
		return -1;
	}
	return stack[top--];
}

void proint_stack(){
	int i;
	printf("\n From Top ---> To Bottom\n\n");
	for(i = top; i >= 0; i--)
		printf(" %-6d", stack[i]);
	puts("\n");
}

void main(void){
	int i;
	init_stack();
	
	printf("\nPush 1, 2, 3\n");
	push(1);
	push(2);
	push(3);
    
	print_stack();
	
	printf("\n pop 수행 후 \n");
	i = pop();
	print_stack();
	printf("\n popped value is %d \n\n", i);

	printf("\n push 4, 5\n");

	push(4);
	push(5);
	print_stack();

	printf("\n Now Stack is full, push 3\n");
	push(3);
	print_stack();

	printf("\n Initialize stack\n");
	init_stack();
	print_stack();

	printf("\n Now Stack is empty, pop\n");
	i = pop();
	print_stack();
}

 

C언어 실습 실행

 

5. 단순 연결 리스트를 이용한 스택 구현

• 스택의 원소 : 단순 연결 리스트의 노드
• 스택 원소의 순서 : 노드의 링크 포인터로 연결
• push : 리스트의 마지막에 노드 삽입
• pop : 리스트의 마지막 노드 삭제
• 변수 top : 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수
   - 초기 상태 : top = NULL

 

1) 논리적 스택

n번째

...

두 번째

첫 번째

 

top	data	link	data	link	data	link
→	n번째	→	두 번째	→	첫 번째	NULL

 

2) 연산 수행과정

• A, B, C를 순서대로 삽입하면서 스택을 생성한 후에 원소 하나를 삭제하는 과정

1. 공백 스택 생성 : create(stack);
2. 원소 A 삽입 : push(stack, A)
3. 원소 B 삽입 : push(stack, B);
4. 원소 C 삽입 : push(stack, C);
5. 원소 삭제 : pop(stack);

(1) 순서 도식화

1.

top

NULL

2.

top	data	link
→	A	NULL

3.

top	data	link	data	link
→	B	→	A	NULL

4.

top	data	link	data	link	data	link
→	C	→	B	→	A	NULL

5.

top	data	link	data	link
→	B	→	A	NULL

 

 

3) C언어 실습

 

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

// int를 스택 element의 자료형으로 정의

typedef struct STACKNODE {	// 스택의 노드 구조 정의
	int data;	// 정수형 타입 데이터(데이터 필드)
	struct STACKNODE *link;
}SNODE;

SNODE *top;	// 스택의 top 노드를 지정하기 위한 포인터 top 선언

void push(int item) { // 스택 삽입 연산
	
	// 메모리 할당 (할당한 주소 temp에 넣음)
	SNODE *temp = (SNODE *)malloc(sizeof(SNODE));
	
	// 데이터를 temp의 데이터 필드에 넣음
	temp -> data = item;

	// temp의 주소를 top에 넣어줌
	temp -> link = top;
	top = temp;
}

int pop() { // 스택의 삭제 후 반환 연산
	int item;
	SNODE *temp = top;

	if (top == NULL) { // 현재 스택이 공백 리스트인 경우
		printf("\n\n Stack is empty.\n");
		return 0;
	}
	else {	// 현재 스택이 공백 리스트가 아닌 경우
		item = temp -> data;	// item에 temp의 데이터를 줌
		top = temp -> link;	// top에 temp의 링크를 줌(밑의 원소를 가리키게 됨)
		free(temp);	// 메모리에서 삭제
		return item;	// 자룟값 리턴
	}
}

int peek() {	// 스택의 top 원소 검색 연산
	int item;
	if (top == NULL) {	// 현재 스택이 공백 리스트인 경우
		printf("\n\n Stack is empty.\n");
		return 0;
	}
	else {	// 현재 스택이 공백 리스트가 아닌 경우
		item = top -> data;	// top의 값을 item에 넣어줌
		return item;	// top의 값 리턴
	}
}

void del() {
	SNODE *temp;
	if (top == NULL) {	// 현재 스택이 공백 리스트인 경우
		printf("\n\n Stack is empty.\n");
	}
	else {	// 현재 스택이 공백 리스트가 아닌 경우
		temp = top;
		top = top -> link;
		free(temp);	// 메모리 삭제
	}
}

void printStack() {	// 스택의 내용 출력 연산
	SNODE *p = top;	// p는 top이랑 같음
	printf("\n 스택 ");
	while (p) {	// NULL이 아닐 때까지
		printf("%d ", p -> data);
		p = p -> link; // 다음 주소로
	}
	printf(" ");
}

void main(void) {
	int item;	// 초깃값 item 선언, top은 NULL로 초기화
	top = NULL;

	printStack();
	push(1);
	printStack();
	push(2);
	printStack();
	push(3);
	printStack();

	item = peek();
	printStack();
	printf("\t peek top => %d", item);

	del();
	printStack();

	item = pop();
	printStack();
	printf("\t pop top => %d", item);

	item = pop();
	printStack();
	printf("\t\t pop top => %d", item);
	pop();
}