[Linked List] 1102 : 스택 (stack)

※ 해당 문제는 C언어 표준 라이브러리만 사용하여 작성한 코드와 풀이 방법입니다.

Stack은 "더미"란 뜻을 가진다.

책 더미, 신문 더미 등에 사용하는 단어이다.

책 더미를 예로 들어 보자.

책 더미를 쌓았다고 했을 때, 이 책 더미에서 책을 가져오는 가장 정상적인 방법은 제일 위에 있는 책을 가져오는 방식이다.

다시 말하면 가장 먼저 들어간 책은 가장 나중에 꺼낼 수 있을 것이다.

이런 식으로 자료가 가장 밑에 쌓이고(입력). 자료를 가져올 때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack 하고 한다.

이러한 Stack의 특징 때문에 흔히 "FILO(First-In-Last-Out : 선입 후출)" 혹은 "LIFO(Last-In-First-Out : 후입 선출)"라고 한다.

그림과 같이 Stack을 설계하고 다음의 처리 조건에 맞는 출력을 하시오.

<처리 조건>
주어진 명령은 다음의 3가지이다.
1. "i a"는 a라는 수를 스택에 넣는다. 이때, a는 10,000 이하의 자연수이다.
2. "o"는 스택에서 데이터를 빼고, 그 데이터를 출력한다. 만약 스택이 비어있으면, "empty"를 출력한다.
3. "c"는 스택에 쌓여있는 데이터의 수를 출력한다.

첫 줄에 N이 주어진다. N은 주어지는 명령의 수이다. (1≤N≤100) 둘째 줄부터 N+1줄까지 N개의 명령이 주어지는데, 한 줄에 하나씩 주어진다.

각 명령에 대한 출력 값을 한 줄에 하나씩 출력한다. 출력내용이 하나도 없는 경우는 주어지지 않는다.

입력 예	출력 예
7 i 7 i 5 c o o o c	2 5 7 empty 0

Solving Talk

1.input과 output의 시작점인 dummy data list인 head를 생성

2. input시 newData의 next는 head의 next 연결.
head의 next에 newData 연결.

3. out시 head의 next 데이터를 pop.
pop data의 next를 head의 next로 연결.

 

Code

#include<stdio.h>

struct Data
{
	int value;
	Data* next;

	Data* allocate(int data)
	{
		value = data;
		return this;
	}

}dataBuffer[110], head;

int dataBuffercnt;
int stackCount;

void input(int data)
{
	//1.new data allocate
	Data* newData = dataBuffer[dataBuffercnt++].allocate(data);

	//2.head의 next를 new Data의 next로 연결
	newData->next = head.next;

	//3.head의 next로 new Data 연결
	head.next = newData;

	//4.stack count 증가
	stackCount++;
}

void out()
{

	if (stackCount == 0)
	{
		printf("empty\n");
		return;
	}

	Data* popData = head.next;
	printf("%d\n", head.next->value);

	//1.head의 next를 popData의 next로 연결.
	head.next = popData->next;
	//2. stack Count --;
	stackCount--;
}

void getCount()
{
	printf("%d\n", stackCount);
}
int main()
{
	int N=0;
	int value;
	char cmd;

	dataBuffercnt = 0;
	stackCount = 0;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf(" %c", &cmd);

		switch (cmd)
		{

		case 'i':
			scanf("%d", &value);
			input(value);
			break;

		case 'o' :
			out();
			break;

		case 'c':
			getCount();
			break;
		}
	}

	return 0;
}

 

문제 출처

JUNGOL | 스택 (stack) > 문제은행