스택

 자료구조에는 여러 형식으로 데이터를 저장한다. 그리고 데이터를 저장하는 방식에 따라 선형형식, 비선형형식으로 나뉜다.

• 선형 구조 : 데이터를 1:1 관계로 하나씩 나열시킨 구조로, list, stack, queue가 해당 구조에 해당한다.
• 비선형 구조 :  데이터를 1:n 관계로 나열 시킨 구조로, Heap, Tree가 해당 구조에 해당한다.

 이중, 데이터의 순서를 바꾸거나 데이터의 순서를 역으로 사용해야 하는 경우에 사용하는 자료구조가 있는데, 이 자료구조가 스택(stack)이다. 스택이란 데이터를 쌓아올린 듯한 형식을 가진 자료구조로, 가장 나중에 삽입되는 데이터가 제일 먼저 삭제되는 형식인 후입선출 형식을 사용한다.

 

 스택에서는 데이터의 삽입을 "push", 데이터의 삭제를 "pop", 가장 나중에 삽입된 데이터를 "top"이라고 한다.

 

배열 스택

 배열 스택이란 배열을 이용해서 스택을 나타내는 자료구조로, 저장공간이 정해져 있는 스택이다.

typedef struct ArrayStackNodetype {
	int data;
}ArrayStackNode;

 위의 구조는 노드의 형태로, 해당 노드 형태로 배열을 만들어서, 스택을 구현할 것이다. 이때, node(노드)란 데이터를 저장하는 공간으로, 구조체를 통해 노드에 어떤 형태의 데이터를 저장할지 결정한다.

 

배열 스택 알고리즘

 스택은 데이터가 제일 나중에 삽입한 데이터는 제일 먼저 삭제되어야 하기에, 데이터를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 소스코드로 구현해야 한다. 이때 top은 마지막 데이터가 위치하는 배열의 인덱스 값을 지정하며, 배열을 생성할 때, "-1"로 구현해야 한다. 그리고 이는 해당 배열이 공백상태이기 때문이다.

 

• 데이터 삽입 함수(push())
  • 기능 
    • 배열에 자리가 있는 경우 : 배열에 데이터를 삽입, top을 +1
    • 배열에 자리가 없는 경우 : 배열에 자리가 없다고 출력
  • 함수의 자료형 : void
  • 매개변수 : 저장할 데이터

알고리즘

1. 배열에 자리가 없을 경우(top = 최대 인덱스) "자리없음"을 출력 2. 배열에 자리가 있을 경우     1-1. top의 위치를 변경     1-2. top의 위치에 데이터 삽입

void push(element item) {
	if (top == STACKSIZE - 1) {
		printf("자리 없음");
	}
	else {
		stack[++top].data = item;		
	}; //top를 증가시킨후 현 top에 원소 삽입

 

• 데이터 삭제 함수(pop())
  • 기능 
    • 배열이 공백이 아닌 경우 : 데이터를 삭제, top을 -1
    • 배열에 공백 인 경우 : 배열에 저장되어 있는 데이터가 없다고 출력
  • 함수의 자료형 : int

알고리즘

1.배열이 공백인 경우(top = -1) "공백상태"를 출력 2. 배열에 자리가 있을 경우     1-1. top의 위치에 데이터 삭제     1-2. top의 위치 변경

int pop() {
	if (top == -1) {//공백상태 확인
		printf("공백상태");
		return;
	}
	else {
		ArrayStackNode temp = { stack[top].data };
		stack[top--].data = 0;
		return temp.data;
	};//현재 top원소 제거한 후 top 감소
}

 

• 데이터 출력 함수(printStack())
  •  기능 : 처음부터 top의 위치까지의 데이터 내용을 출력

알고리즘	인덱스 값이 "1"인 배열 요소 부터 top까지 출력

void printStack(void) {;
	printf("\nstack : ");
	for (int i = 0; i <= top; i++) {
		printf("%d\t", stack[i]);
	}
	printf("]");
}

 

 

 데이터 삽입, 데이터 삭제, 데이터 출력하는 함수를 구현했으며, 해당 함수들을 통해 배열 스택을 생성하면 다음과 같다.

#include<stdio.h>
#define STACKSIZE 5


typedef int element;

typedef struct ArrayStackNodetype {
	int data;
}ArrayStackNode;

ArrayStackNode stack[STACKSIZE];

int top = -1;

int isStackEmpty(void) { //Stack 데이터 유무 확인
	if (top == -1)
		return;
	else
		return 0;
}

int isStackFull(void) { //Stack 데이터 초과 확인
	if (top == STACKSIZE - 1) { 
		return;
	}
	else
		return 0;
}

//데이터 삽입
void push(element item) {
	if (isStackFull()) {
		printf("자리 없음");
	}
	else {
		stack[++top].data = item;
	}; //top를 증가시킨후 현 top에 원소 삽입
}

//데이터 삭제
element pop() {
	if (isStackEmpty()) {//공백상태 확인
		printf("삭제원소 없음");
		return;
	}
	else {
		ArrayStackNode temp = { stack[top].data };
		stack[top--].data = 0;
		return temp.data;
	};//현재 top원소 제거한 후 top 감소
}

//데이터 출력
void printStack(void) {;
	printf("\nstack :[ ");
	for (int i = 0; i <= top; i++) {
		printf("%d\t", stack[i]);
	}
}

int main() {
	element item;
	printStack();

	push(1);
	printStack();
	push(2);
	printStack();
	push(3);
	printStack();

	item = pop();
	printStack();
	printf("\t pop : %d", item);
}

 

연결 스택

 연결 스택은 노드의 주소를 통해 연결되어 있는 스택으로, 저장공간이 한정되어 있는 배열 스택과는 달리, 주소로 연결되어 있기에, 제한 없이 데이터를 저장 할 수 있다.

typedef struct LinkedStackNodeType {
	element data;
	struct LinkedStackNodeType* link;
}LinkedstackNode;

 위의 구조는 노드의 구조체로, 노드가 연결되어 있어야 하기에 노드의 구조체에 다음 노드의 주소를 저장하는 공간이 필요하다.

 

연결 스택 알고리즘

 스택은 데이터가 제일 나중에 삽입한 데이터는 제일 먼저 삭제되어야 하기에, 데이터를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 소스코드로 구현해야 한다. 이때 top는 가장 마지막의 노드의 주소를 저장하며, 처음에는 데이터가 없기에 "NULL"을 저장한다. 그리고 이는 해당 연결 스택이 공백상태이기 때문이다.

 

• 데이터 삽입 함수(push())
  • 기능 
    • 데이터가 저장되어 있는 노드를 추가, top에 추가되는 값은 노드의 주소
  • 함수의 자료형 : void
  • 매개변수 : 저장할 데이터
  • 필드 사용 변수
    1. temp ← 새로운 노드의 주소를 저장하는 포인터 변수

알고리즘

1. 새로운 노드를 생성하고 해당 노드에 데이터 저장 2. 마지막 노드에 저장되어 있는 주소값을 새로운 노드의 주소값에 저장 3. top에 새로운 노드의 주소를 저장

void push(element item) {
	LinkedStackNode* temp = (LinkedStackNode*)malloc(sizeof(LinkedStackNode));
	temp->data = item;
	temp->link = top;
	top = temp;
}

 

• 데이터 삭제 함수(pop())
  • 기능 
    • top의 저장된 주소가 null이 아닐 경우 : 해당 주소의 노드에 저장된 주소값을 top에 저장
    • top의 저장된 주소가 null일 경우 : 저장되어 있는 노드가 없다고 출력
  • 함수의 자료형 : int
  • 필드 사용 변수
    1. temp ← 새로운 노드의 주소를 저장하는 포인터 변수

알고리즘

1. top에 저장되어 있는 주소인 삭제할 노드에 저장된 주소값을 top에 저장 2. 동적 변수로 되어있는 노드 삭제

element pop() {
	if (isStackEmpty()) {
		printf("노드가 없음\n");
		return 0;
	}
	else {
		LinkedStackNode* temp = top;
		element item = temp->data;
		top = top->link;
		free(temp);
		return item;
	}
}

 

• 데이터 출력 함수(printStack())
  •  기능 : top의 위치에서 부터 저장된 주소값이 NULL인 노드의 데이터 내용을 출력

알고리즘	top에 저장된 주소의 노드의 데이터를 시작으로, 노드에 저장되어 있는 주소를 따라 데이터 출력

void printStack() {
	LinkedStackNode* p = top;
	printf("\n stack :");
	while (p != NULL) {
		printf("\t%d", p->data);
		p = p->link;
	}
	printf("]");
}

 

 데이터 삽입, 데이터 삭제, 데이터 출력하는 함수를 구현했으며, 해당 함수들을 통해 배열 스택을 생성하면 다음과 같다.

#include<stdio.h>
#include<stdlib.h>
typedef int element; //스택 원소의 자료형

typedef struct LinkedStackNodeType {
	element data;
	struct LinkedStackNodeType* link;
}LinkedStackNode;

LinkedStackNode* top;

// 공백 검출
int isStackEmpty(void) {
	if (top == NULL)
		return;
	else
		return 0;
}

//추가노드 연결
void push(element item) {
	LinkedStackNode* temp = (LinkedStackNode*)malloc(sizeof(LinkedStackNode));
	temp->data = item;
	temp->link = top;
	top = temp;
}
//노드 삭제
element pop() {
	if (isStackEmpty()) {
		printf("스택이 비어있음\n");
		return 0;
	}
	else {
		LinkedStackNode* temp = top;
		element item = temp->data;
		top = top->link;
		free(temp);
		return item;
	}
}
//스택 출력
void printStack() {
	LinkedStackNode* p = top;
	printf("\n stack :");
	while (p != NULL) {
		printf("\t%d", p->data);
		p = p->link;
	}
	printf("]");
}

int main() {
	
	element item;
	printStack();

	push(1);
	printStack();
	push(2);
	printStack();
	push(3);
	printStack();

	item = pop();
	printStack();
	printf("\t pop : %d", item);

	item = pop();
	printStack();
	printf("\t pop : %d", item);

	item = pop();
	printStack();
	printf("\t pop : %d", item);

	return 0;
}