Data Structure : Stack

자료구조(출처 및 참고)

---

Link

dnf-lover.tistory.com/entry/자료구조-자료구조의-선형-비선형-분류에-따른-각-종류와-자료구조별-특징-간단-정리

참고

Stack & Queue

---

Stack

---

스택은 삽입 순서와 삭제 순서가 역순이 되도록 자료를 구조화하는 조건과 연산 방식을 정의한 자료구조.

스택의 특징은 First In Last Out(FILO) 형식

스택의 구현은 배열을 이용한 순차 자료구조와 포인터를 사용하는 연결 자료구조 방식이 있음.

스택의 가장 마지막 삽입 위치를 가리키는 포인터 top

스택의 자료 입력 명령어인 push

스택의 자료 출력/반환 명령어인 pop

스택의 현재 top의 원소 출력 명령어인 peek

---

Linear Stack

---

#include <stdio.h>
#define STACK_SIZE 100;

typedef int element;
element stack[STACK_SIZE];
int top=-1;

int isStackEmpty(void) {
	if(top==-1) return 1;
	else return 0;
}

int isStackFull(void) {
	if(top == STACK_SIZE-1) return 1;
	else return 0;
}


void push(element item) {
	if(isStackFull()) {
		printf("\nStack Full!\n");
		return;
	}
	stack[++top]=item;
}

element pop(void) {
	if(isStackEmpty()) {
		printf("\nStack Empty!\n");
		return;
	}
	else return stack[top--];
}

element peek(void) {
	if(isStackEmpty()) {
		printf("\nStack Empty!\n");
		return;
	}
	else return stack[top];
}

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

---

Linked list + Stack

---

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

typedef int element;
typedef struct stackNode {
	element data;
	struct stackNode* link;
} stackNode;

stackNode* top=NULL;

int isStackEmpty(void) {
	if(top==NULL) return 1;
	else return 0;
}

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

element pop(void) {
	element item;
	stackNode* ret=top;
	if(isStackEmpty()) {
		printf("\nStack Empty!\n");
		return 0;
	}
	else {
		item=ret->data;
		top=ret->link;
		free(ret);
		return item;
	}
}

element peek(void) {
	if(isStackEmpty()) {
		printf("\nStack Empty!\n");
		return 0;
	}
	else {
		return top->data;
	}
}

void printStack(void) {
	printf("\nStack [");
	stackNode* p=top;
	while(p) {
		printf("%d ",p->data);
		p=p->link;
	}
	printf("]\n");
}

---