스택 (Stack)

(사실 스택과 큐는 C++에서

#include <stack>

#include <queue>

그리고 자바에서

java.util.stack

java.util.queue

을 이용하여 직접적인 구현 없이 사용이 가능합니다)

 

 

 

스택

Stack을 한국어로 번역하면 쌓다, 입니다.

이름에서도 알 수 있듯이 데이터를 접시처럼 쌓고, 맨 아래 접시부터 빼면 접시가 무너지기에.. 접시를 사용하려면 맨 위 접시(데이터)를 빼내야 합니다.

이렇게 나중에 들어간 것이 먼저 나오는 구조를 LIFO (Last-In First-Out. 후입선출) 구조라고 합니다.

 

 

빈 스택입니다.

맨 위를 top, 맨 아래를 bottom이라고 합니다.

스택에 데이터를 넣는 것을 push라고 합니다.

위 그림은 데이터가 하나뿐이므로 데이터=top=bottom인 상태입니다.

데이터가 두 개 이상부터 top과 bottom이 분리됩니다

스택에서 데이터를 빼내는 pop 과정입니다.

top에 있던 데이터를 삭제하고 top은 그 아래 데이터를 가리킵니다.

가장 나중에 들어간 것이 먼저 나오는 구조임을 파악할 수 있습니다.

 

 

 

배열을 이용한 스택 구현

배열을 이용한 스택 구현입니다.

배열의 크기를 미리 정해야 하기 때문에 배열을 이용한 스택 또한 정해진 크기 내에서만 이용할 수 있습니다.

 

0 구조체 정의+초기화

#include<iostream>
using namespace std;

typedef struct _stack{
	int arr[10];
	int top;
	int NumOfData;

}Stack;

void Initialize(Stack *s){
	s->top = -1;
	s->NumOfData = 0;
}

1 Push

void Push(Stack *s, int data){
	if (!isFull(s)){
		(s->top)++;
		s->arr[s->top] = data;
		(s->NumOfData)++;
	}
	else{
		cout << "스택이 차 있어 값을 넣을 수 없습니다" << endl;
	}
}

 

2 pop

void Pop(Stack *s){
	if (isEmpty(s)){
		cout << "스택이 비어 있어 Pop할 수 없습니다" << endl;
		return;
	}

	int result = s->arr[s->top];
	(s->top)--;
	(s->NumOfData)--;

	cout << "Popped: " << result << endl;
}

2.5 isFull?

bool isFull(Stack *s){
	if (s->NumOfData == 10)
		return true;
	return false;
}

 

3 isEmpty?

bool isEmpty(Stack *s){
	if (s->NumOfData == 0)
		return true;
	return false;
}

 

 

3.5 peek (Top 데이터 출력)

void Peek(Stack *s){
	cout << "Peek: " << s->arr[s->top] << endl;
}

 

4 데이터 출력

void ShowStack(Stack *s){

	if (isEmpty(s)){
		cout << "스택이 비어 있어 출력할 수 없습니다" << endl;
		return;
	}
	
	int i = s->top;

	cout << "*****스택의 Top부터 출력합니다" << endl;

	while (i>=0){
		cout << s->arr[i] << " ";
		i--;
	}

	cout << endl << endl;
}

5 테스트용 메인 함수 + 결과 (결과는 맨 밑 연결리스트와 동일합니다)

int main(){

	Stack s;

	Initialize(&s);

	if (isEmpty(&s))
		cout << "스택이 비었습니다" << endl;

	Push(&s, 1);
	Push(&s, 2);
	Push(&s, 3);
	ShowStack(&s);

	Pop(&s);
	ShowStack(&s);
	
	Peek(&s);
	ShowStack(&s);

	if (isEmpty(&s))
		cout << "스택이 비었습니다" << endl;

	return 0;
}

 

 

 

 

 

 

저는 양방향 리스트를 응용했습니다.

연결 리스트를 이용한 스택 구현

 

0 구조체 + 초기화

#include<iostream>
using namespace std;

typedef struct _node{
	int data;
	struct _node *next;
	struct _node *before;
}Node;

typedef struct _stack{
	Node *top;

	int NumOfData;

}Stack;

void Initialize(Stack *s){
	s->top = NULL;
	s->NumOfData = 0;
}

 

1 Push

void Push(Stack *s, int data){
	
	Node *newnode = (Node*)malloc(sizeof(Node));
	newnode->data = data;
	newnode->next = NULL;
	newnode->before = NULL;

	if (!isEmpty(s)) {
		s->top->next = newnode;
		newnode->before = s->top;
	}
	s->top = newnode;
	(s->NumOfData)++;
}

 

2 pop

void Pop(Stack *s){
	if (isEmpty(s)){
		cout << "스택이 비어 있어 Pop할 수 없습니다" << endl;
		return;
	}

	Node *Dummy = (Node*)malloc(sizeof(Node));
	Dummy = s->top;
	int result = Dummy->data;
	s->top = s->top->before;
	s->top->next = NULL;

	free(Dummy);

	(s->NumOfData)--;

	cout << "Popped: " << result << endl;

}

 

3 isEmpty?

bool isEmpty(Stack *s){
	if (s->NumOfData == 0)
		return true;
	return false;
}

 

3.5 Peek (Top 데이터 출력)

void Peek(Stack *s){
	cout << "Peek: "<<s->top->data << endl;
}

 

4 데이터 출력

void ShowStack(Stack *s){
	if (isEmpty(s)){
		cout << "스택이 비어 있어 출력할 수 없습니다" << endl;
		return;
	}

	Node *current = (Node*)malloc(sizeof(Node));
	current = s->top;

	cout << "*****스택의 Top부터 출력합니다" << endl;

	while (current != NULL){
		cout << current->data << " ";
		current = current->before;
	}

	cout << endl << endl;
}

 

5 테스트용 메인 함수 + 결과

int main(){

	Stack *s = (Stack*)malloc(sizeof(Stack));

	Initialize(s);

	if (isEmpty(s))
		cout << "스택이 비었습니다" << endl;

	Push(s, 1);
	Push(s, 2);
	Push(s, 3);
	ShowStack(s);

	Pop(s);
	ShowStack(s);
	
	Peek(s);
	ShowStack(s);

	if (isEmpty(s))
		cout << "스택이 비었습니다" << endl;

	return 0;
}

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

참고용으로 봐주시고 부족한 부분은 지적 부탁드립니다

감사합니다~~