[알고리즘] 스택 (Stack)

[알고리즘] 스택 (Stack)

---

LIFO(Last In First Out) 나중에 들어온 것이 먼저 나가는 구조로 FIFO의 큐와는 반대되는 개념을 가지고 있다.

소스코드 구현 (C++ / STL)

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	stack<int> s;
	s.push(3);
	s.push(4);
	s.pop();
	s.push(3);
	s.push(1);
	s.pop();
	s.push(3);
	s.push(2);
	s.pop();

	while (!s.empty())
	{
		cout << s.top() << ", ";
		s.pop();
	}
	return 0;
}

stack = { }; ← 3 넣기

stack = { 3 }; ← 4 넣기

stack = { 3, 4 }; ← 빼기

stack = { 3 }; 가장 나중에 들어왔던 4가 빠짐

 ⁞

출력 결과

소스코드 구현 (C)

#include <stdio.h>

struct Stack
{
	int arr[10000];
	int last;

	void init() {
		last = -1;
	}

	void push(int data) {
		arr[++last] = data;
	}

	bool empty() {
		return last < 0;
	}

	void pop() {
		if (!empty())
		{
			arr[last] = -1;
			last--;
		}
	}
	
	int size() {
		return last + 1;
	}

	int top() {
		if (empty()) return -1;
		else return arr[last];
	}
};

int main()
{
	Stack s;
	s.init();

	s.push(3);
	s.push(4);
	s.pop();
	s.push(3);
	s.push(1);
	s.pop();
	s.push(3);
	s.push(2);
	s.pop();

	while (!s.empty())
	{
		printf("%d ", s.top());
		s.pop();
	}

	return 0;
}

출력

---

스택은 STL 라이브러리를 사용하는 방법이 있다. 하지만 LIFO라는 개념을 이해하기 위해서 C코드로 직접 구현해보았다. 스택은 프링글스 과자라고 생각하면 될것 같다. 먼저 들어간 과자는 통 맨아래로 내려가 있으며 가장 마지막에 들어온 과자는 최상단에 놓이게 되며 이것이 push의 개념이다. 그후 소비자가 과자를 먹으면 가장 최상단에 있는 과자를 먹게되고 이것이 pop의 개념이 된다.