스택(Stack)

해당 포스트는 이지스퍼블리싱, 『알고리즘 코딩테스트 자바 편』, Gene 김종관 을 참고하여 작성하였습니다.

스택의 정의

최근에 저장한 데이터를 먼저 사용하는 구조로 LIFO(Last In First Out) 구조라고 칭함.

후입 선출 또는 LIFO(last in, first out)는 컴퓨터 과학과 대기 이론에서 어떠한 종류의 데이터 구조에 저장되어 있는 항목들이 처리되는 것을 말한다. LIFO 구조화 선형 목록에서, LIFO 요소는 맨 위의 항목만 추가하거나 제거할 수 있다.

---

스택의 용어

자료 구조의 하나로서 자료의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 목록, 밑이 막힌 통을 세워 놓은 것으로 생각하면 된다. 자료의 삽입, 삭제가 일어나는 곳을 스택의 탑(top)이라 하며 자료를 스택에 넣은 것을 푸시(push), 스택에서 자료를 꺼내는 것을 팝(pop)이라 한다. 스택에서는 나중에 들어간 자료가 먼저 꺼내지므로 후입 선출(LIFO)이라고도 한다. 스택은 주로 내용을 기억시켰다가 다시 이용하고자 할 때 사용되며, 컴퓨터 알고리즘에서 자주 쓰이는 중요한 자료구조이다.

• PUSH
  PUSH는 스택에 자료를 삽입하기 위해서 사용하는 명령으로, 스택의 가장 위에 자료가 쌓이게 됩니다.

  스택을 구현할 때 스택 포인터 (Stack Pointer)를 지정하게 되는데,
  스택포인터는 보통 가장 마지막에 쌓인 자료의 위치 또는 다음에 쌓일 자료의 위치를 가리킵니다.
  따라서 PUSH 명령은 스택 포인터 또는 스택 포인터 다음 위치에 자료를 삽입하는 형태로 구현됩니다.

• POP
  POP은 스택에 쌓인 자료를 꺼내기 위해서 사용하는 명령으로, 스택의 가장 위에 있는 자료를 꺼냅니다.

  PUSH와 마찬가지로 스택 포인터가 가리키는 자료를 꺼내거나, 스택 포인터가 가리키는 자료를 꺼내는 형태로 구현됩니다.

• PEEK
  PEEK은 스택에 쌓인 자료 중 가장 위에 쌓인 자료를 읽기 위해서 사용하는 명령입니다.
  
  

  POP 명령은 데이터를 꺼냄과 동시에 삭제하는 반면에,
  PEEK 명령은 데이터를 꺼내기만 하고 삭제는 하지 않습니다.

• EMPTY
  EMPTY는 스택이 비어 있다면 TRUE, 비어있지 않다면 FALSE를 리턴하는 명령입니다.

• Stack Overflow
  Stack Overflow는 스택이 가득차 있을 때 PUSH 명령을 수행하면 발생하는 오류입니다.

• Stack Underflow
  Stack Underflow는 스택이 비어있을 때 POP 명령을 수행하면 발생하는 오류입니다.

---

스택의 구현

스택은 간단한 자료구조인만큼 간단한 알고리즘으로 구현이 가능합니다.
구현하는 방법은 보통 배열과 리스트를 많이 사용하는데, 스택을 사용하는 경우에 수많은 저장 공간을 요구하는데 사용되지 않기 때문에 보통 크기가 결정되어 있는 배열로 간단한 구현하는 경우가 많습니다.

• 배열을 이용해 스택 'StackArray.c'

#include<stdio.h>
#define SIZE 6

int stack[SIZE] = {0, };
int top = -1;

int push(int data){
	if (top == SIZE-1){
		printf("stack overflow!\n");
		return -1;
	}
	stack[++top] = data;

	return 0;
}

int pop(void){
	if (top == -1){
		printf("stack underflow!\n");
		return -1;
	}

	return stack[top--];
}

int main(void){
	//정상적으로 push()됨
	push(10); push(20); push (30); push (40); push (50); push (60);

	//overflow 발생으로 push()되지 않고, ’stack overflow!’를 출력
	push (70);

	//정상적으로 pop()됨
	printf("1st pop: %d\n", pop()); printf("2nd pop: %d\n", pop());
	printf("3rd pop: %d\n", pop());

	//정상적으로 push()됨
	push(80);

	// 정상적으로 pop()됨
	printf("4th pop: %d\n", pop()); printf("5th pop: %d\n", pop());
	printf("6th pop: %d\n", pop()); printf("7th pop: %d\n", pop());

	//top은 -1이므로 underflow 발생. ‘stack underflow!’를 출력하고 리턴받은 -1도 출력함
	printf("8th pop: %d\n", pop());

	return 0;
}

• 연결 리스트를 사용한 스택 'stackLinkedList.c'

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

struct node{
	int data;
	struct node *link;
};

struct node *top = NULL;
int cnt = 0;

int push(int data){
	struct node *addNode;

	if(cnt >= SIZE){
		printf("Stack Overflow!\n");
		return -1;
	}

	addNode = (struct node *)malloc(sizeof(struct node));
	addNode->data = data;
	addNode->link = top;
	top = addNode;
	cnt++;

	return 0;
}

int pop(void){
	int data;
	struct node *delNode=top;

	if(top == NULL){
		printf("Stack Underflow!\n");
		return -1;
	}

	data = top->data;
	top = top->link;
	free(delNode);
	cnt--;

	return data;
}

int main(void){
	struct node *freeNode;

	push(10); push(20); push(30);
	printf("POP: %d\n", pop());
	push(40); push(50);

	printf("스택 유효 데이터(top에서 base까지): ");	
	while(top != NULL){
		printf("%d, ", top->data);
		freeNode = top;
		top = top->link;
		free(freeNode);
	}

	return 0;
}

---

스택의 사용의 예

1. 실생활에서의 스택

실생활에서 스택과 비슷한 현상을 많이 찾아볼 수 있습니다.

• 책을 쌓아 놓을 경우 가장 위에 있는 책부터 꺼낼 수 있다.
• 막다른 길에 차를 주차한 경우 가장 마지막에 주차한 차부터 나올 수 있다.

2. 프로그래밍에서의 스택

프로그래밍에서 '스택'이라는 자료구조를 사용하는 경우는 생각보다 많습니다.

• 브라우저의 '뒤로가기'
  이동하는 페이지를 뒤로가기 스택에 쌓아두었다가 뒤로가기 버튼을 누르면 스택에서 꺼내서 그 페이지로 이동한다.

• Ctrl + Z (Undo)
  Ctrl + Z를 누르면 실행된 수행을 취소하고 이전의 상태로 되돌립니다.
  이는 스택에 이전의 상태를 차곡히 저장해두었다가
  스택에서 가져와서 이전의 상태로 복구하기 때문에 가능합니다.
  메모장에서는 이러한 스택의 크키가 하나(그냥 하나만 저장하는듯),
  타 에디터(한글, word, ppt)의 경우에는 큰 스택의 크키를 가지고 있고
  Ctrl + Z 를 여러번 사용해보면 스택의 크기에 제한이 있다는 것을 알 수 있습니다.

• C나 Java의 메모리의 경우에 Stack이라는 공간이 존재하는데,
  이 Stack과 여기서 말하는 스택은 같은 의미의 스택입니다.
  함수 안에서 함수를 호출하는 경우 그 함수 스택이 쌓여,
  후에 호출된 함수가 처리를 마쳐야 전에 호출된 함수가 마저 실행될 수 있습니다.

---