[자료구조] 스택(Stack)이란?

연결리스트를 배우면서 연결리스트로 구현한 스택에 대해서도 배워서, 직접 연결리스트로 스택을 구현해보려고 하던 중에 그냥 스택에 대해서도 블로그에 써 놓는게 더 도움이 될 것 같아서 스택부터 정리한 후 아래에 연결리스트로 스택을 구현해 보아야겠다.

 

스택이란?

스택은 기본적으로 후입선출(Last In First Out)을 기반으로 한 선형 구조이다.

이런 구조는 한쪽 끝에서만 자료의 출입이 이루어지기 때문에 기본적으로 push() 와 pop()연산이 필수적으로 필요하다.

여기서 push()는 '데이터를 밀어 넣는다'는 개념으로 데이터를 추가하는 입력 연산이고,

pop()은 자료가 튀어나오는 것을 의미하여 출력 연산을 지칭한다.

그 외에도 조회 연산인 peek가 있는데 이 연산은 가장 마지막으로 들어간 데이터를 반환하며 삭제하지않는다.

아래의 그림은 연결리스트의 노드로 스택을 구현한 형태를 그림으로 나타낸 것이다.

연결리스트로 구현한 스택

 

이제 C언어를 이용해 연결리스트로 스택를 구현해보자.

간단하게 삽입, 삭제, 크기, 마지막 데이터를 반환, 첫 데이터를 반환하는 기능들을 구현해 보았다.

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

typedef int Element; //데이터 별명
typedef struct LinkNode { //노드 생성
	Element data;
	struct LinkNode* link; //노드의 주소값을 저장 (*구조체의 자기참조)
} node;

node* top = NULL; //스택의 top 선언

void push(Element e) { //삽입연산을 하는 함수
	if (top == NULL) { //데이터를 스택에 처음 삽입할 때
		top = (node*)malloc(sizeof(node));
		if (top != NULL) {
			top->data = e;
			top->link = NULL;
		}
	}
	else { //이미 스택안에 데이터가 있을 때
		node* obj = (node*)malloc(sizeof(node));
		if (obj != NULL) {
			obj->data = e;
			obj->link = top; //새로 만든 노드에 이전 데이터 주소 삽입
			top = obj; //top 새로 지정
		}
	}
}

Element pop() { //출력 연산을 하는 함수
	Element e = top->data;
	node* obj = top->link;
	free(top);
	top = obj;
	return e;
}

int size() { //스택의 크기를 구하는 함수
	int cnt = 0;
	node* curr = top;
	while (curr != NULL) {
		cnt++;
		curr = curr->link;
	}

	return cnt;
}

Element peek() { //스택의 마지막 데이터 반환 함수
	return top->data;
}

Element front() { //스택의 가장 앞의 데이터 반환 함수
	node* curr = top;
	while (curr->link != NULL) {
		curr = curr->link;
	}
	return curr->data;
}

int main() {
	printf("size() = %d ", size());
	push(1);
	printf("size() = %d ", size());
	push(2);
	printf("size() = %d \n", size());
	push(3);
	printf("back() = %d ", peek());
	printf("front() = %d ", front());
	printf("size() = %d ", size());
	printf("pop() = %d\n", pop());

	printf("size() = %d ", size());
	printf("pop() = %d\n", pop());

	printf("size() = %d ", size());
	printf("pop() = %d\n", pop());

	return 0;
}