数据结构——栈总结
顺序栈
表示
#define MAXSIZE 100
typedef struct {
SElemType *base; //栈底指针(表头端)
SelemType *top; //栈顶指针(表尾端)
int stacksize; //栈可用最大容量
}SqStack;
初始化
Status InitStack(SqStack &S) {
//构造一个空栈
S.base = (SElemType*)malloc(MAXSIZE*sizeof*(SElemType));
if (!S.base)
exit (OVERFLOW); //存储分配失败
S.top = S.base; //栈顶指针等于栈底指针
S.stacksize = MAXSIZE;
return OK;
}
判断是否为空
Status StackEmpty(SqStack S) {
if (S.top == S.base) //栈为空标志：S.top == S.base
return TRUE;
else
return FALSE;
}
清空
Status ClearStack(SqStack &S) {
if (S.base)
S.top = S.base;
return OK;
}
销毁
Status Destroy(SqStack &S) {
if (S.base){
free S.base;
S.stacksize = 0;
S.base = S.top = NULL;
}
}
入栈
Status Push(SqStack &S, SElemType e) {
if (S.top - S.base == S.stacksize) //栈满
return ERROR;
*S.top++ = e; //*S.top = e; S.top++;
return Ok;
}
出栈
Status Pop(SqStack &S, SElemType &e) {
if (S.top == S.base) //栈为空
return ERROR;
e = *--S.top; //--S.top; e = *S.top
return OK;
}
获取栈顶元素值
Status GetTop(SqStack S, SElemType &e) {
if (S.top == S.base)
return ERROR;
e = *(S.top-1);
return OK;
}
链栈
表示
- 链表的头指针就是栈顶
- 不需要头结点
- 基本不存在栈满的情况
- 空栈相当于头指针指向空
- 插入和删除仅在栈顶出执行
typedef struct StackNode {
SElemType data;
struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;
初始化
void InitStack(LinkStack &S) {
S = NULL; //空栈，栈顶指针置空
return OK;
}
判断是否为空
Status StackEmpty(LinkStack S) {
if (S == NULL)
return TRUE;
else
return FALSE;
}
入栈
Status Push(LinkStack &S, SElemType e) {
StackNode *p;
p->data = e; //将新结点数据域置为 e
p->next = S; //将新结点插入栈顶
S = p; //修改栈顶指针
return OK;
}
出栈
Status Pop(LinkStatck &S, SElemType e) {
if (S == NULL)
return ERROR;
e = S->data;
p = S;
S = S->next;
}
C语言实现代码
顺序栈
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5 /* 栈最大容量 */
#define Empty 0 /* 空 */
#define Full 1 /* 满 */
#define Avail -1 /* 可用 */
typedef struct sta
{
int *top; /* 栈顶指针 */
int *base; /* 栈底指针 */
int stacksize; /* 栈的最大容量 */
}SqStack;
SqStack InitStack (SqStack p); // 初始化栈
SqStack Push (SqStack p); //入栈
SqStack Pop (SqStack p); // 出栈
void DisplyStack (SqStack p); // 遍历栈中元素
int StackEmpty (SqStack p); // 判断栈是否为空
int StackFull (SqStack p); // 判断栈是否为满
int main()
{
SqStack p;
char ch;
p.stacksize = MAX_SIZE;
p = InitStack (p); /* 初始化栈 */
//入栈
printf("你想要添加元素吗到栈吗? (Y/N)\n");
scanf(" %c", &ch);
while (ch == 'Y' || ch == 'y')
{
p = Push (p); /* 入栈 */
DisplyStack (p);/* 打印栈中元素 */
printf("你想要添加元素吗到栈吗?(Y/N)\n");
scanf(" %c", &ch);
}
//出栈
printf("你想出栈吗？(Y/N)\n");
scanf(" %c", &ch);
while (ch == 'Y' || ch == 'y')
{
p = Pop (p);
DisplyStack (p);
printf("你想出栈吗？(Y/N)\n");
scanf(" %c", &ch);
}
return 0;
}
//初始化
SqStack InitStack (SqStack p)
{
p.base = (int *)malloc(p.stacksize * sizeof(int));
if (p.base == NULL)
{
printf("初始化栈失败\n");
exit(0);
}
p.top = p.base;
p.stacksize = MAX_SIZE;
return p;
}
//入栈
SqStack Push (SqStack p)
{
int data;
if (StackFull(p) == Full)
{
printf("栈空间已满，无法入栈");
return p;
}
printf("输入数字：");
scanf("%d", &data);
*p.top = data;
p.top++; //*p.top++ = data
return p;
}
//出栈
SqStack Pop (SqStack p)
{
int data;
if (StackEmpty(p) == Empty)
{
printf("栈为空栈，无法出栈 ");
return p;
}
// p.top--;
// printf("出栈元素为：%d\n", *p.top);
data = *--p.top;
printf("出栈元素为：%d\n",data);
return p;
}
//判断栈是否为空
int StackEmpty (SqStack p)
{
if (p.top == p.base)
{
return Empty;
}
else
{
return Avail;
}
}
//判断栈是否为满
int StackFull (SqStack p)
{
if (p.top - p.base == p.stacksize)
{
return Full;
}
else
{
return Avail;
}
}
//遍历栈中元素，从栈顶到栈底
void DisplyStack (SqStack p)
{
if (StackEmpty(p) == Empty)
{
printf("栈为空栈，无法遍历\n");
return;
}
printf("栈中元素为:\n");
printf("顶端 [");
while (p.top != p.base)
{
//p.top--;
//printf("%d",*p.top);
printf("%d", *--p.top);
}
printf("] 底端\n");
}
链栈
#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack {
int data;
struct StackNode *next;
}StackNode, *LineStack;
LineStack push(LineStack S, int a); //入栈
LineStack pop(LineStack S); //出栈
int main() {
LineStack S = NULL;
S = push(S, 1);
S = push(S, 2);
S = push(S, 3);
S= push(S, 4);
S = pop(S);
S = pop(S);
S= pop(S);
S = pop(S);
S = pop(S);
return 0;
}
//入栈
LineStack push(LineStack S, int a) {
//创建存储新元素的节点
StackNode* line = (LineStack)malloc(sizeof(StackNode*));
line->data = a;
//新节点与头节点建立逻辑关系
line->next = S;
//更新头指针的指向
S = line;
return S;
}
//出栈
LineStack pop(LineStack S) {
if (S) {
//声明一个新指针指向栈顶节点
StackNode* p = S;
//更新头指针
S = S->next;
printf("出栈元素：%d ", p->data);
if (S) {
printf("新栈顶元素：%d\n", S->data);
}
else {
printf("栈已空\n");
}
free(p);
}
else {
printf("栈内没有元素(空栈)");
return S;
}
return S;
}
--> 顺序栈表示#define MAXSIZE 100typedef struct { SElemType *base; //栈底指针(表头端) SelemType *top; //栈顶指针(表尾端) int stacksize; //栈可用最大容量}SqStack; 初始化Status InitStack(SqStack &S) { //构造一个空...