반응형
스택이란
선입후출(First-In-Last-Out) 형태의 자료 구조.
스택은 더미라는 의미로 건초 더미를 쌓아 올린 형태를 가진 자료 구조.
상자를 차곡 차곡 쌓아올린 형태로 가장 위에 상자를 치워야 아래 상자를 꺼낼 수 있는 구조.
삽입과 제거가 주요입니다.
스택은 배열과 링크드 리스트로 구현 할 수 있습니다.
 |  |
배열 형태의 스택 / 링크드 리스트 형태의 스택
C 소스
Array Stack
ArrayStack.h
/*
* array_stack.h
*
* Created on: 2018. 12. 31.
* Author: otrodevym
*/
#ifndef ARRAY_STACK_H_
#define ARRAY_STACK_H_
#define NULL (void *)0
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct tagNode{
ElementType Data;
}Node;
typedef struct tagArrayStack{
int Capacity;
int Top;
Node* Nodes;
} ArrayStack;
void AS_CreateStack(ArrayStack** Stack, int Capacity);
void AS_DestroyStack(ArrayStack* Stack);
void AS_Push(ArrayStack* Stack, ElementType Data);
ElementType AS_Pop(ArrayStack* Stack);
ElementType AS_Top(ArrayStack* Stack);
int AS_GetSize(ArrayStack* Stack);
int AS_IsEmpty(ArrayStack* Stack);
#endif /* 2_1_ARRAY_STACK_ARRAY_STACK_H_ */
ArrayStack.c
/*
* array_stack.c
*
* Created on: 2018. 12. 31.
* Author: otrodevym
*/
#include "ArrayStack.h"
void AS_CreateStack(ArrayStack** Stack, int Capacity) {
(*Stack) = (ArrayStack*) malloc(sizeof(ArrayStack));
(*Stack)->Nodes = (Node*) malloc(sizeof(Node) * Capacity);
(*Stack)->Top = 0;
(*Stack)->Capacity = Capacity;
}
void AS_DestroyStack(ArrayStack* Stack) {
free(Stack->Nodes);
free(Stack);
}
void AS_Push(ArrayStack* Stack, ElementType Data) {
int Position = Stack->Top;
Stack->Nodes[Position].Data = Data;
Stack->Top++;
}
ElementType AS_Pop(ArrayStack* Stack) {
int Position = --(Stack->Top);
return Stack->Nodes[Position].Data;
}
ElementType AS_Top(ArrayStack* Stack) {
int Position = Stack->Top - 1;
return Stack->Nodes[Position].Data;
}
int AS_GetSize(ArrayStack* Stack) {
return Stack->Top;
}
int AS_IsEmpty(ArrayStack* Stack) {
return (Stack->Top == 0);
}
main.c
/*
* main.c
*
* Created on: 2018. 12. 31.
* Author: otrodevym
*/
#include "ArrayStack.h"
int ArrayStack_main() {
int i = 0;
ArrayStack* Stack = NULL;
AS_CreateStack(&Stack, 10);
AS_Push(Stack, 3);
AS_Push(Stack, 37);
AS_Push(Stack, 11);
AS_Push(Stack, 12);
printf("Capacity : %d, Size : %d, Top : %d \n\n", Stack->Capacity,
AS_GetSize(Stack), AS_Top(Stack));
for (i = 0; i < 4; i++) {
if (AS_IsEmpty(Stack)) {
break;
}
printf("Poped : %d, ", AS_Pop(Stack));
if (!AS_IsEmpty(Stack)) {
printf("Current Top : %d \n", AS_Top(Stack));
} else {
printf("Stack Is Empty. \n");
}
}
AS_DestroyStack(Stack);
return 0;
}
LinkedList
LinkedListStack.h
/*
* linked_list_stack.h
*
* Created on: 2018. 12. 31.
* Author: otrodevym
*/
#ifndef LINKED_LIST_STACK_H_
#define LINKED_LIST_STACK_H_
#define NULL (void *) 0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tagNode{
char* Data;
struct tagNode* NextNode;
} Node;
typedef struct tagLinkedListStack{
Node* List;
Node* Top;
} LinkedListStack;
void LLS_CreateStack(LinkedListStack** Stack);
void LLS_DestroyStack(LinkedListStack* Stack);
Node* LLS_CreateNode(char* Data);
void LLS_DestroyNode(Node* _Node);
void LLS_Push(LinkedListStack* Stack, Node* NewNode);
Node* LLS_Pop(LinkedListStack* Stack);
Node* LLS_Top(LinkedListStack* Stack);
int LLS_GetSize(LinkedListStack* Stack);
int LLS_IsEmpty(LinkedListStack* Stack);
#endif /* 2_2_LINKED_LIST_STACK_LINKED_LIST_STACK_H_ */
LinkedListStack.c
/*
* linked_list_stack.c
*
* Created on: 2018. 12. 31.
* Author: otrodevym
*/
#include "LinkedListStack.h"
void LLS_CreateStack(LinkedListStack** Stack){
(*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
(*Stack)->List = NULL;
(*Stack)->Top = NULL;
}
void LLS_DestroyStack(LinkedListStack* Stack){
while( !LLS_IsEmpty(Stack)){
Node* popped = LLS_Pop(Stack);
LLS_DestroyNode(popped);
}
free(Stack);
}
Node* LLS_CreateNode(char* NewData){
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = (char*)malloc(strlen(NewData)+1);
strcpy(NewNode->Data, NewData);
NewNode->NextNode = NULL;
return NewNode;
}
void LLS_DestroyNode(Node* _Node){
free(_Node->Data);
free(_Node);
}
void LLS_Push(LinkedListStack* Stack, Node* NewNode){
if(Stack->List == NULL){
Stack->List = NewNode;
}else{
Node* OldTop = Stack->List;
while(OldTop->NextNode != NULL){
OldTop = OldTop->NextNode;
}
OldTop->NextNode = NewNode;
}
Stack->Top = NewNode;
}
Node* LLS_Pop(LinkedListStack* Stack){
Node* TopNode = Stack->Top;
if(Stack->List == Stack->Top){
Stack->List = NULL;
Stack->Top = NULL;
}else{
Node* CurrentTop = Stack->List;
while((CurrentTop != NULL) && (CurrentTop->NextNode != Stack->Top)){
CurrentTop = CurrentTop->NextNode;
}
Stack->Top = CurrentTop;
CurrentTop->NextNode = NULL;
}
return TopNode;
}
Node* LLS_Top(LinkedListStack* Stack){
return Stack->Top;
}
int LLS_GetSize(LinkedListStack* Stack){
int Count = 0;
Node* Current = Stack->List;
while(Current != NULL){
Current = Current->NextNode;
Count++;
}
return Count;
}
int LLS_IsEmpty(LinkedListStack* Stack){
return (Stack->List == NULL);
}
main.c
/*
* linked_list_stack_main.c
*
* Created on: 2018. 12. 31.
* Author: otrodevym
*/
#include "LinkedListStack.h"
int LinkedListStackMain(){
int i = 0;
int Count = 0;
Node* Popped;
LinkedListStack* Stack;
LLS_CreateStack(&Stack);
LLS_Push(Stack, LLS_CreateNode("abc"));
LLS_Push(Stack, LLS_CreateNode("def"));
LLS_Push(Stack, LLS_CreateNode("efg"));
LLS_Push(Stack, LLS_CreateNode("hij"));
Count = LLS_GetSize(Stack);
printf("Size : %d, Top : %s \n\n", Count, LLS_Top(Stack)->Data);
for(i = 0; i < Count; i++){
if(LLS_IsEmpty(Stack)){
break;
}
Popped = LLS_Pop(Stack);
printf("Popped: %s ", Popped->Data);
LLS_DestroyNode(Popped);
if(!LLS_IsEmpty(Stack)){
printf("Current Top : %s \n", LLS_Top(Stack)->Data);
}else{
printf("Stack IS Empty \n");
}
}
LLS_DestroyStack(Stack);
return 0;
}
Java 소스
ArrayStack
ArrayStack.java
package b_stack;
public class ArrayStack {
private int top;
private int size;
private Node[] nodes;
public ArrayStack(int size) {
this.top = -1;
this.size = size;
this.nodes = new Node[size];
}
class Node{
private int value;
public Node(int value) {
this.value = value;
}
}
private void push(int value) {
this.top++;
Node newNode = new Node(value);
this.nodes[this.top] = newNode;
}
private int pop() {
int data = this.nodes[this.top].value;
this.nodes[this.top] = null;
this.top--;
return data;
}
public static void main(String args[]) {
ArrayStack list =new ArrayStack(3);
list.push(1);
list.push(2);
list.push(3);
System.out.println(list.pop());
System.out.println(list.pop());
System.out.println(list.pop());
}
}
LinkedList
LinkedList.java
package b_stack;
public class LinkedListStack<T> {
private int size;
private Node top;
class Node{
private T value;
private Node nextNode;
public Node(T value) {
this.value = value;
this.nextNode = null;
}
}
public LinkedListStack() {
this.size = 0;
this.top = null;
}
public void push(T value) {
Node newNode = new Node(value);
newNode.nextNode = top;
top = newNode;
this.size++;
}
public T pop() {
T data = this.top.value;
this.top = this.top.nextNode;
this.size--;
return data;
}
public static void main(String args[]) {
LinkedListStack<String> stack = new LinkedListStack<>();
stack.push("1");
stack.push("2");
stack.push("3");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
반응형
'개발(합니다) > 컴퓨터 일반&CS' 카테고리의 다른 글
| [자료구조]트리(Tree) (0) | 2019.01.03 |
|---|---|
| [자료구조]큐(Queue) (0) | 2019.01.02 |
| [연산자표기법]전위 표기법, 중위 표기법, 후위 표기법 (0) | 2018.12.31 |
| [자료구조] 환형 링크드 리스트(Circular Linked List) (0) | 2018.12.30 |
| [자료구조]더블 링크드 리스트(Doubly Linked List) (0) | 2018.12.30 |
