[자료구조] stack

stack

1. stack

 

stack(스택)은 출입구가 하나로 통일된 선형 자료구조이다.

즉, 데이터의 삽입 및 삭제가 한 곳에서만 일어난다.

스택은 위의 그림처럼 한 쪽(우리는 이를 top이라 부른다)만 뚫려 있는 기다란 통과 같은 구조이다.

그림을 통해 삽입 과정을 이해해보자.

 

int형 데이터를 담는 스택에 차례로 5, 4, 2, 1을 삽입해보자.

 

입구가 하나이므로 삽입하는 순서대로 그림처럼 스택에 쌓일 것이다.

제일 위에 있는 원소 1은 당연히 제일 마지막에 삽입한 원소이다.

이 원소의 위치를 스택의 top이라 부른다.

 

만약 다음과 같은 스택에서 2에 바로 접근할 수 있을까?

안된다. 2에 접근하기 위해서는 위에 쌓여있는 1을 빼내야만 한다.

1을 빼내고 나면 그다음 원소 2가 top에 위치한다.

따라서 다음 삭제 연산에서는 2가 삭제될 것이다.

여기서 스택의 제일 중요한 성질, LIFO에 대해 알 수 있다.

Last In First Out 늦게 들어올수록 빨리 나간다는 뜻이다.

 

스택은 개념도 간단하고 구현도 간단하다.

구현은 배열로도 할 수 있지만 연결리스트 기반으로 해보았다.

class Node {
public:
	int data;
	Node*next;

	Node(int e) {
		this->data = e;
		this->next = NULL;
	}
};

class Stack {
public:

	Node * head;
	Node * tail;
	int stack_size;

	Stack() {
		head = NULL;
		tail = NULL;
		stack_size = 0;
	}

	void push(int x) {
		Node*cur = new Node(x);
		if (head == NULL) {
			head = cur;
			tail = cur;
		}
		else {
			Node*tmp = head;
			head = cur;
			head->next = tmp;
		}
		stack_size++;
	}

	int pop() {
		if (head == NULL)
			return -1;
		else {
			int item = head->data;
			head = head->next;
			stack_size--;
			return item;
		}
		
	}

	int top() {
		if (head == NULL)
			return -1;
		else {
			int item = head->data;
			return item;
		}
	}

	int size() {
		return stack_size;
	}

	int empty() {
		if (stack_size == 0)
			return 1;
		else
			return 0;
	}
};