[자료구조] Stack📚

LEESEUNGYEOL·2022년 1월 16일

스택(Stack)📚

스택?

책이 쌓여있는 이미지를 생각하면 이해하기 좋습니다.

사전적으로 계속 쌓이다라는 의미가 있습니다.

스택은 일종의 리스트

단, 데이터의 삽입과 삭제가 한쪽 끝에서만 일어납니다.

LIFO(Last In First Out)

삽입/삭제가 일어나는 쪽을 스택의 top이라고 부릅니다.

메서드

IsEmpty()

스택이 비어있으면 True, 아니라면 False를 리턴합니다.
int isempty() {
	if (top == -1) {//top은 -1부터 시작합니다.
		return 1;
	}
	return 0;
}

IsFull()

스택이 가득 찼다면 True, 아니라면 False를 리턴합니다

int isfull() {
	if (top >= capacity - 1) {//top이 가장 큰 사이즈보다 크거나 같으면 가득 찬 것 입니다.
		return 1;
	}
	return 0;
}

push() 🌟

스택의 top에 원소를 하나 추가합니다.

void push(item) {
	if (!isfull()) {//추가 전 확인    
		stack[++top].key = item;//마지막 인덱스인 top의 다음 값을 포인팅 하고(++top) 원소를 넣습니다.
	}
}

pop() 🌟

스택의 top인 원소를 하나 제거합니다.

void pop(item) {
	if (!isempty()) {//제거 전  확인
		element item = stack[top]; //top의 원소를 제거합니다.
		top--;// 포인팅 하는 top을 하나 줄입니다.
	}
}

peek()

스택의 맨 위에 있는 요소를 삭제하지 않고 반환합니다.
int peek(){
	if(!isempty()){
    	return stack[top];
    }
}

stack 구현하기

배열 혹은 연결리스트를 이용하여 구현할 수 있습니다.

배열을 이용한 구현

배열로 구현하는 방법은 간단한 반면에 스택의 크기가 고정되는 약점이 있습니다.

#include <stdio.h>
#define MAX_STACK_SIZE 100

char stack[MAX_STACK_SIZE];
int top = -1; // stack을 저장하는 top index

void push(int key) {
	if (is_full()) {
		return;
	}
	stack[++top] = key;
}

int pop() {
	if (is_empty()) {
		return;
	}
	int tmp = stack[top];
	top--;
	return tmp;
}

char peek() {
	return stack[top];
}
int is_empty() {
	return top == -1;
}
int is_full() {
	return top == MAX_STACK_SIZE - 1;
}

연결리스트를 이용한 구현

연결리스트를 이용한 방법은 구현이 약간 복잡한 반면, 스택의 크기를 필요에 따라 가변적으로 변경할 수 있습니다.

연결리스트의 맨 앞 부분을 스택의 top으로 두는것이 편합니다.

#include <stdio.h>
typedef struct {
	char* data;
	struct NODE* next;
}NODE;
NODE* top = NULL; //가장 첫 노드를 가리킵니다.

//add-first
void push(char* item) {
	NODE* node = (NODE*)malloc(sizeof(NODE));
	node->data = item; 
	node->next = top;
	top = node;
}

//remove-first
char* pop() {
	if (is_empty()) { //비어있다면 NULL반환합니다.
		return NULL;
	}
	char* result = top->data;
	NODE* p = top;
	top = top->next;
	free(p); //삭제할 노드를 없애주는 것이 좋습니다.
	return result;
}

char* peek() {
	if (is_empty()) {
		return NULL;
	}
	return top->data;
}

int is_empty() {
	return top == NULL;
}

문제점

만약 스택이 동시에 2개 이상 필요하다면?

stack 배열과 top이 전역 변수로 선언되기 때문에 전체 프로그램에서 여러개의 스택을 사용하기 어렵다.
-> top과 stack배열을 하나의 구조체로 결합시켜서 이 구조체의 포인터를 합수의 매개변수로 전달한다.

<보완한 코드>
큰 틀만 형성하느라 디테일한 점들은 넣지 않았습니다 감안해주세요 !

#include <stdio.h>
#define MAX_STACK_SIZE 100
typedef int element;
typedef StackType* Stack;
typedef struct { 
	element* stack; //stack 배열 -> 동적할당으로 create 함수에서 만든다
	int top;
	int size; //배열의 크기
}StackType;

Stack create() {
	Stack s = (Stack)malloc(sizeof(StackType));
	s->top = -1;
	s->size = MAX_STACK_SIZE;
	return s;
}

void push(StackType* s, element item) {
	if (is_full(s)) {
		return;
	}
	else s->stack[++(s->top)] = item;
}

element pop(StackType* s) {
	if (is_empty(s)) {
		exit(1);
	}
	else return s->stack[(s->top)--];
}

int main(void) {
	StackType* s1 = create();
	StackType* s2 = create();
	push(s1, 12);
	push(s2, 9);
	return 0;
}