栈
2018-09-11 本文已影响14人
qianranow
0. 顺序存储结构
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
typedef struct Node {
int Data[MAXSIZE];
int Top;
}SNode, *Stack;
// 生成空堆栈
Stack CreateStack(int MaxSize) {
Stack PtrS;
PtrS = (Stack)malloc(sizeof(SNode));
PtrS -> Top = -1;
return PtrS;
}
// 入栈
void Push(Stack PtrS, int item) {
if (PtrS -> Top == MAXSIZE - 1) {
printf("堆栈满");
return;
} else {
PtrS -> Data[++(PtrS -> Top)] = item;
return;
}
}
// 出栈
int Pop(Stack PtrS) {
if (PtrS -> Top == -1) {
printf("堆栈空");
return -2;
} else {
return (PtrS -> Data[(PtrS -> Top)--]);
}
}
typedef struct DNode {
int Data[MAXSIZE];
int Top1;
int Top2;
}DSNode, *DStack;
// 生成空堆栈
DStack CreateDStack(int MaxSize) {
DStack PtrS;
PtrS = (DStack)malloc(sizeof(DSNode));
PtrS -> Top1 = -1;
PtrS -> Top2 = MAXSIZE;
return PtrS;
}
void DPush(DStack PtrS, int item, int Tag) {
if (PtrS -> Top2 - PtrS -> Top1 == 1) {
printf("堆栈满");
return;
}
if (Tag == 1) {
PtrS -> Data[++(PtrS -> Top1)] = item;
} else {
PtrS -> Data[--(PtrS -> Top2)] = item;
}
}
int DPop(DStack PtrS, int Tag) {
if (Tag == 1) {
if (PtrS -> Top1 == -1) {
printf("堆栈1空");
return -2;
} else {
return PtrS -> Data[(PtrS -> Top1)--];
}
} else {
if (PtrS -> Top2 == MAXSIZE) {
printf("堆栈1空");
return -2;
} else {
return PtrS -> Data[(PtrS -> Top2)++];
}
}
}
1. 链式存储结构
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *Next;
}SNode, *Stack;
Stack CreateStack() {
Stack S;
S = (Stack)malloc(sizeof(SNode));
S -> Next = NULL;
return S;
}
int IsEmpty(Stack S) {
return (S -> Next == NULL);
}
void Push(int item, Stack S) {
Stack TmpCell;
TmpCell = (Stack)malloc(sizeof(SNode));
TmpCell -> data = item;
TmpCell -> Next = S -> Next;
S -> Next = TmpCell;
}
int Pop(Stack S) {
Stack FirstCell;
int TopItem;
if (IsEmpty(S)) {
printf("堆栈空");
return -2;
} else {
FirstCell = S -> Next;
S -> Next = FirstCell -> Next;
TopItem = FirstCell -> data;
free(FirstCell);
return TopItem;
}
}
