[자료구조] 스택 Stack [C++]

스택(Stack)의 개념

후입선출(LIFO)의 자료구조. 가장 마지막으로 저장소로 들어온 데이터가 먼저 나가는 구조의 자료구조이다.

 

스택(Stack)의 기본 구조

Push로 저장소에 데이터를 추가하고, Pop을 통해 데이터를 삭제한다. 삭제될 데이터는 항상 위에 있으며, top이라고 부른다.

 

스택(Stack) 구현

#include <iostream>

using namespace std;

#define SIZE 10

int list[SIZE];
int top = -1;

void Enqueue(int);
int Dequeue();

int main()
{
	cout << "(1) push. (2) pop (3) Print (4) Exit" << endl;
	int menu;
	cin >> menu;

	while (menu != 4)
	{
		switch (menu)
		{
		case 1:
		{
			int temp;
			cout << "Enter a push value:";
			cin >> temp;

			Enqueue(temp);
		}
			break;
		case 2:
		{
			cout << Dequeue() << "is pop" << endl;
		}
		break;
		case 3:
		{
			for (int i = 0; i <= top; i++)
			{
				cout << "[" << i + 1 << "]" << list[i] << " ";
			}
			cout << endl;
		}
		break;
		default:
			cout << "Wrong Input!" << endl;
		}

		cout << "(1) Enqueue. (2) Dequeue (3) Print (4) Exit" << endl;
		cin >> menu;
	}
}

void Enqueue(int val)
{
	if (top >= SIZE - 1)
		return;

	list[++top] = val;
}

int Dequeue()
{
	if (top < 0)
		return -1;

	return list[top--];
}

스택을 배열로 구현하게 되면 저장 크기가 제한적이다. 이를 보완하기위해 링크드리스트로 구현하겠다.

 

스택(Stack) 링크드리스트 구현

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

typedef struct node								
{
	int val;									
	node* next;									
}NODE;											

void Push(NODE ** top, int val);
int Pop(NODE ** top);
int Stack_Empty(NODE * top);
int Stack_Full(NODE * top);
void Print(NODE* top);

using namespace std;

int main()
{
	NODE * stack = NULL;
	while (1)						
	{
		int n;
		cout << "Push(1)  Pop(2)  print(3) exit(4): ";
		cin >> n;			

		switch (n)					
		{
		case 1:						
		{
			if (Stack_Full(stack))
			{
				cout << "Stack is Full";
				break;
			}
			int temp;
			cout << "Enter a integer please: ";
			cin >> temp;
			Push(&stack, temp);
		}
		break;
		case 2:						
		{
			if (Stack_Empty(stack))
			{
				cout << "Stack is Empty";
				break;
			}
			int temp = Pop(&stack);
			cout << temp <<  " is deleted";
		}
		break;
		case 3:						
		{
			Print(stack);
		}
		break;
		case 4:						
		{
			return 0;
		}
		default:					
			cout << "error";
			break;
		}
		printf("\n");
	}

	return 0;
}

//[push]
//description: appends data to the stack
//input: double pointer of top node, data to append
//output: none
void Push(NODE ** top, int val)
{
	NODE * newNode = (NODE*)malloc(sizeof(NODE));		
	newNode->val = val;									
	newNode->next = *top;								

	*top = newNode;										
}

//[pop]
//description: removes data from the stack
//input: double pointer of top node
//output: data on top of the stack
int Pop(NODE ** top)
{
	NODE * temp = *top;									
	int tValue = temp->val;								
	*top = temp->next;									

	free(temp);											

	return tValue;										
}

//[stack_empty]
//description : checks array is empty or not
//input: top node
//output: return 0 when array is not empty or return -1 when array is empty
int Stack_Empty(NODE * top)
{
	return top == NULL;									
}

//[stack_full]
//description: checks array is full or not
//input: top node
//output: return -1 when array is full or return 0 when array is not full
int Stack_Full(NODE * top)
{
	struct stack *test = (struct stack *)malloc(sizeof(struct stack *));

	if (test == NULL)
		return 1;
	else
	{
		free(test);
		return 0;
	}
}

//[Print]
//description; print all elements of stack
//input: top node
//output: none
void Print(NODE * top)
{
	if (!Stack_Empty(top))								
	{
		cout << top->val << " ";						
		Print(top->next);								
	}
}