[자료구조] 3. 스택 (Stack)

 

스택(Stack)은 모든 원소들의 삽입(insert, push)과 삭제(delete, pop)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료구조(linear data structure)이다.

 

삽입과 삭제가 일어나는 끝은 Top이라고 하고, 반대편 끝을 Bottom이라고 한다.

 

스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, top에서 원소를 제거 하는 것을 pop이라고 한다.

 

push와 pop은 top에서 일어나기 때문에 top의 포인터를 증가 또는 감소시키면서 수행한다.

 

이렇듯 스택은 나중에 들어간 것이 먼저 나오는 구조이기 때문에 '후입선출' 방식의 자료구조이다.

영어로는 LIFO(Last-In, First-out)라고도 불린다.

 

 

 

스택

 

스택을 구현할 때에는 크게 4가지가 필요하다.

 

1. 스택이 empty인지 확인하는 함수

2. 스택이 full인지 확인하는 함수

3. push함수

4. pop함수

5. top을 가리키는 포인터

 

 

스택을 구현할 때 배열을 사용하거나 연결리스트를 사용하는데, 기능적인 부분을 고려하면 거의 연결리스트로 구현을 한다.

 

 

 

 

배열 기반 스택

 

 

 

연결리스트 기반 스택

 

문제

 

학생들의 <학번, 이름, 점수>를 명단에 보관한다. 수용 한도는 10명이며, 최대 10개의 엔트리를 가지는 스택을 구현해보고자 한다.

 

(1) 다음 학생들을 순서대로 스택에 넣어보자

<10, 은우, 100>, <20, 수지, 90>, <36, 예슬, 93>, <15, 시아, 75>, <3, 예원, 89>, <22, 현진, 96>,

<17, 서정, 90>, <7, 은탁, 77>

 

(2) 3명을 자료구조의 성격대로 차례로 명단에서 삭제해보자

 

(3) 다음 학생들을 차례로 명단에 넣어보자. 그리고 전체 학생들의 명단을 출력해보자.

<30, 시연, 72>, <4, 도일, 84>, <25, 용주, 100>, <6, 민재, 76>

 

(4) 6명을 자료구조의 성격대로 명단에서 삭제해보자. 이들을 삭제 순으로 출력해보자.

 

(5) 남아있는 학생들을 입력 순으로 출력해보자.

 

 

> 배열 기반 스택

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define TRUE 1
#define FALSE 0
#define MAX 10

typedef int bool;

typedef struct {
	int id;
	char name[30];
	int score;
}student;

student list[10];

int top = -1;

bool isEmpty();
bool isFull();
void push(student);
student pop();

int main(void)
{
	student temp, out;
	
	printf("명단에 넣을 학생들의 학번, 이름, 점수를 순서대로 입력하세요 (종료: -1)\n");
	
	while (1) {
		fscanf(stdin, "%d %s %d", &temp.id, &temp.name, &temp.score);
		
		if (temp.id == -1)
			break;

		push(temp);
	}

	// 3명 삭제
	printf("\n3명을 삭제한다\n\n");
	pop();
	pop();
	pop();

	// 추가 입력
	printf("추가로 명단에 넣을 학생들의 학번, 이름, 점수를 순서대로 입력하세요 (종료: -1)\n");

	while (1) {
		fscanf(stdin, "%d %s %d", &temp.id, &temp.name, &temp.score);

		if (temp.id == -1)
			break;

		push(temp);
	}

	// 6명 삭제
	printf("\n6명을 삭제한다\n");
	for (int i = 0; i < 6; i++) {
		out = pop();
		printf("<%d, %s, %d>\n", out.id, out.name, out.score);

	}

	//남아있는 학생들 출력
	printf("\n남은 학생 목록\n");
	
	for (int i = 0; i <= top; i++) {
		printf("<%d, %s, %d>\n", list[i].id, list[i].name, list[i].score);
	}
	
}

bool isEmpty() // 스택이 empty인지 확인하는 함수
{
	if (top == -1)
		return TRUE;

	else
		return FALSE;
		
}

bool isFull() // 스택이 full인지 확인하는 함수
{
	if (top == MAX)
		return TRUE;

	else
		return FALSE;
}

void push(student temp)
{
	if (isFull() == TRUE)
	{
		printf("stack is full. cannot push!\n");
		exit(1);
	}

	else
	{
		list[++top] = temp;
	}
}

student pop()
{
	if (isEmpty() == TRUE)
	{
		printf("stack is empty. cannot pop!\n");
		exit(1);
	}
	
	else
	{
		top--;
		return list[top + 1];
	}
}

/*
10 은우 100
20 수지 90
36 예슬 93
15 시아 75
3 예원 89
22 현진 96
17 서정 90
7 은탁 77
-1 -1 -1


30 시연 72
4 도일 84
25 용주 100
6 민재 76
-1 -1 -1
*/