[자료구조] 스택(Stack)

CS/자료구조

[자료구조] 스택(Stack)

내꺼블로그 2024. 4. 12. 14:57

스택(Stack)

자료구조의 한 종류로 나중에 삽입된 원소가 먼저 삭제되는 LIFO(Last In First Out) 성질을 가지고 있다.

스택에서 연산이 일어나는 끝 부분을 top이라고 하며, top에서 삽입(push), 삭제(pop)가 일어난다.

시스템에서는 함수 호출이 일어난 이후 가장 최근 호출된 함수로 돌아가기 위해서 사용된다.

=>스택 메모리의 스택이 이 녀석임.

스택(Stack) 구현: 배열

배열로 구현된 코드는 다음과 같다.

#define MAX_SIZE 1000
#include<iostream>

using namespace std;

int stack[MAX_SIZE];
int top = 0;

bool IsEmpty();
bool IsFull();
void Push(int num);
int Pop();
int Peek();

int main()
{
	cout<<Pop()<<endl;
	Push(1);
	Push(5);
	Push(7);
	cout << Pop() << endl;
	cout << Peek() << endl;
	Push(4);
	cout << Pop() << endl;
	cout << Pop() << endl;
	cout << Pop() << endl;
}

bool IsEmpty()
{
	return top == 0;
}

bool IsFull()
{
	return top == MAX_SIZE;
}

void Push(int num)
{
	if (IsFull()) {
		cout << "스택이 가득 찼습니다." << endl;
		return;
	}
	stack[top++] = num;
}

int Pop()
{
	if (IsEmpty()) {
		cout << "스택이 비어있습니다.";
		return -128;
	}
	return stack[--top];
}

int Peek()
{
	if (IsEmpty()) {
		cout << "스택이 비어있습니다.";
		return -128;
	}
	return stack[top - 1];
}

스택의 역할을 해줄 배열(stack)과 top의 인덱스이다.

(사실 top값에 -1을 할당해주는 것이 더 정석인것 같다만 구현에 따라 차이가 좀 있음)

스택이 가득 찼다면 아래의 문구를 출력해주고 그렇지 않다면 top위치에 num을 할당해주고 top을 다음 인덱스로 넘긴다.

top이 MAX_SIZE와 값이 같은지를 bool 형태로 return

같은 값이라면 스택에 할당된 크기만큼 값들이 전부 다 할당된 상태, 즉 가득 찼단 상태가 되므로 이 때는 true를 반환해준다.

만약 스택에 값이 비어있다면 아래의 문구를 출력

그렇지 않다면 top의 값을 1 감소하고 해당 인덱스의 값을 반환

스택이 비어있다면 아래의 문구를 출력

그렇지 않다면 top 바로 아래 인덱스의 값을 반환

Pop과 달리 Peek은 값을 삭제하지 않으므로 top의 값 자체를 변화시키지 않음

top==0 -> 스택이 비어있음을 의미

스택이 비어있다면(top의 값이 0이라면) true를 반환, 아니라면 false를 반환

결과

스택(Stack) 구현: 연결 리스트

연결 리스트로 구현된 코드는 다음과 같다.

#include<iostream>

using namespace std;

typedef struct node
{
	int item;
	node* next;
}node;

typedef struct stack
{
	node* top;
}stack;

bool IsEmpty(stack* s);
bool IsFull(node* n);
void Push(stack* s, int num);
int Pop(stack* s);
int Peek(stack* s);

int main()
{
	stack* s = (stack*)malloc(sizeof(stack));
	s->top == NULL;
	Push(s, 1);
	Push(s, 5);
	cout << Pop(s) << endl;
	cout << Peek(s) << endl;
	cout << Pop(s) << endl;
	Push(s, 6);
	Push(s, 8);
	cout << Peek(s) << endl;
	cout << Pop(s) << endl;
}

bool IsEmpty(stack* s)
{
	return s->top == NULL;
}

bool IsFull(node* n)
{
	return n == NULL;
}

void Push(stack* s, int num)
{
	node* temp = (node*)malloc(sizeof(node));
	if (IsFull(temp)) {
		cout << "Stack Overflow" << endl;
		return;
	}
	temp->item = num;
	temp->next = s->top;
	s->top = temp;
}

int Pop(stack* s)
{
	if (IsEmpty(s)) {
		cout << "Stack Underflow" << endl;
		return -128;
	}
	node* temp = s->top;
	int item = temp->item;
	s->top = temp->next;
	free(temp);
	return item;
}

int Peek(stack* s)
{
	if (IsEmpty(s)) {
		cout << "Stack Underflow" << endl;
		return -128;
	}
	return s->top->item;
}