스택(Stack)

스택(Stack)

데이터들을 쌓아서 올려놓은 형태를 가지는 자료구조이다.

 

스택의 특징

 - 데이터의 삽입과 삭제가 top이라 부르는 데이터 말단에서만 이루어진다.

 - 들어오는 시간 순서에 따라 데이터가 쌓이고, 마지막에 삽입된 데이터가 먼저 삭제되는 후입선출(LIFO: Last In First Out)의 구조를 가진다.

 

스택의 활용

 - 실행 취소(Undo)

 - 후위 표기법 계산

 - 재귀 알고리즘

---

스택의 추상 자료형

 

데이터

 

연산

init(): 스택의 초기화

isEmpty(): 스택이 비어있는지 확인

push(): 요소삽입

pop(): 마지막 요소 반환 및 삭제

peek(): 마지막 요소 반환

size(): 요소의 개수 반환

---

아래는 c에서 연결 리스트를 기반으로 한 스택의 구현입니다.

#include <stdio.h>
#include <stdlib.h>

typedef int Data;

typedef struct node {
	Data data;
	struct Node* next;
} Node;

Node* top = NULL;

void init() {
	top = NULL;
}

int isEmpty() {
	if (top == NULL) return 1;
	else return 0;
}

int push(Data data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = top;
	top = newNode;
}

int pop() {
	Node* node;
	Data data;
	
	node = top;
	top = node->next;
	data = node->data;
	free(node);
	return data;
}

int peek() {
	return top->data;
}

int size() {
	Node* node;
	int count = 0;
	for (node = top; node != NULL; node = node->next)	count++;
	return count;
}

int main() {

	init();

	printf("isEmpty: %d\n\n", isEmpty());

	for (int i = 0; i < 5; i++) {
		printf("%d 삽입\n", i);
		push(i);
	}
	
	printf("\npeek: %d\n", peek());
	printf("size: %d\n", size());

	printf("\npop 수행\n", pop());

	printf("peek: %d\n", peek());
	printf("size: %d\n", size());

	return 0;
}