백준 8958번, 언어 : C/C++

문제설명

 

문제출처 : www.acmicpc.net/problem/10828

10828번: 스택

간략한 설명 : Stack을 구현할 수 있는지에 대한 문제.

메인 필요지식 : 자료구조 Stack

 

문제풀이 아이디어

 

Stack을 연결리스트를 이용해서 구현.

배열을 이용해서 구현해도 되지만, 동적으로 할당하고 싶어서 연결리스트를 이용했다.

사전에 구현되어 있는 C++의 Stack 표준 라이브러리를 사용해도 되지만, Stack을 복습하는 차원에서

처음부터 끝까지 구현해 보았다.

 

 

 

예시 입출력

입력)                                            출력)

6                     

push 2                       

push 3

top      -------------------------------------------> 3

pop     -------------------------------------------->3

pop     -------------------------------------------->2

pop     -------------------------------------------->-1

 

---

<실제 실행 결과>

 

 

코드

 

#include<stdlib.h>
#include<cstring>
#include<iostream>

using namespace std;

//연결리스트로 stack 구현

typedef struct _node
{
	int data;
	struct _node* next=NULL;
}Node;

typedef struct _stack
{
	Node* head = NULL;
	int numOfData = 0; //stack에 존재하는 data의 수 표시

}Stack;

//push 함수
void push(Stack* pstack, int data)
{
	if (pstack->head == NULL) //stack이 비어있는 경우
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->next = NULL;
		pstack->head = newNode;
		pstack->head->data = data;
		(pstack->numOfData)++;
	}
	else //stack이 비어있지 않는 경우에 head부분에 새로운 노드 추가
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->next = NULL;
		newNode->data = data;
		newNode->next = pstack->head;
		pstack->head = newNode;
		(pstack->numOfData)++;
	}
}

//pop연산
int pop(Stack* pstack)
{
	Node* removeNode;
	int removeData;

	//stack이  비어있는 경우 -1을 반환
	if (pstack->head == NULL) return -1;

	removeNode = pstack->head; //삭제할 노드 
	removeData = pstack->head->data; //삭제할 노드의 데이터
	pstack->head = pstack->head->next; //삭제할 노드의 그 다음 노드를 head가 가리킴.

	free(removeNode); //할당해제
	(pstack->numOfData)--; //data의 개수 하나 감소
	return removeData; 
}

//stack의 size 반환
int size(Stack* pstack)
{
	return pstack->numOfData;
}


//stack이 비어있는지 유무 확인
int empty(Stack* pstack)
{
	if (pstack->head == NULL) return 1; //비어있다면 1 반환
	else return 0; //비어있지 않다면 0 반환
}

//stack의 제일 위에 있는 data 반환
int top(Stack* pstack)
{	
	if (pstack->head == NULL) return -1; //반환할 data가 없다면 -1 리턴
	else return pstack->head->data;
}

int main()
{	
	Stack stack;
	stack.head = NULL; //stack의 head를 NULL로 초기화
	int N;
	int data;
	char str[6];
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> str;

		//각각의 입력 경우에 따라서 알맞은 함수를 실행
		if (!strcmp(str, "push"))
		{	
			cin >> data;
			push(&stack, data);
		}
		else if (!strcmp(str, "pop"))
		{
			cout << pop(&stack)<<endl;
		}
		else if (!strcmp(str, "size"))
		{
			cout << size(&stack) << endl;
		}
		else if (!strcmp(str, "empty"))
		{
			cout << empty(&stack) << endl;
		}
		else if (!strcmp(str, "top"))
		{
			cout << top(&stack) << endl;
		}
		else //예상외의 입력을 했을 시 예외처리
		{
			printf("commend is not exist, error! \n");
			exit(-1);
		}
	}
	//혹시나 모를 메모리 누수를 막기 위해서 확실하게 할당 해제
	while (!(stack.head == NULL))
	{
		Node* remove = NULL;
		remove = stack.head;
		stack.head = stack.head->next;
		free(remove);
	}
	return 0;
}

 

코드에 대한 질문이 있을 시 댓글로 남겨주세요.

 

더 많은 문제의 코드 : github.com/Ewlrma/Algorithm-Solution-

Ewlrma/Algorithm-Solution-