本文参考自《大话数据结构》

栈与队列

栈是限定只能在表尾进行插入和删除操作的线性表；队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表；

1.栈的定义

​ 我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不包含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LIFO（Last In First Out）结构。

栈的插入操作，叫做进栈，也称压栈，入栈；栈的删除操作，叫做出栈，也有的叫做弹栈；

2.栈的抽象数据类型

把插入和删除操作改名为push和pop；

ADT 栈(stack) Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。 Operation InitStack(*S)：初始条件，建立一个空栈S； DestroyStack(*S)：若栈存在，则销毁它； ClearStack(*S)：将栈清空； StackEmpty(S)：若栈为空，返回true，否则返回false； GetTop(S,*e)：若栈存在且非空，用e返回S的栈顶元素； Push(*S,e)：若栈S存在，插入新元素e到栈S中并成为栈顶元素； Pop(*S,*e)：删除栈S中栈顶元素，并用e返回其值； StackLength(S)：返回栈S的元素个数 endADT

3.栈的顺序存储结构及实现

定义一个top变量来指示栈顶元素在数组中的位置，top可以上下移动，但无论如何都不能超出存储栈的长度（StackSize），即top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。

栈的结构定义

typedef int SElemType; //SElemType类型根据实际情况而定，这里假设为int */ typedef struct { SElemType data[MAXSIZE]; int top; //用于栈顶指针 }SqStack;

进栈操作push

/* 插入元素e为新的栈顶元素 */ Status Push(SqStack *S, SElemType e) { if(S->top == MAXSIZE-1) //栈满 return ERROR; S->top++; //栈顶指针+1 S->data[S->top] = e; return OK; }

出栈操作pop

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR */ Status Pop(SqStack *S, SElemType *e) { if(S->top == -1){ return ERROR; } *e = S->data[S->top]; //将要删除的栈顶元素赋值给e S->top--; //栈顶指针-1 return OK; }

两者没有涉及到循环语句，所以时间复杂度为O(1)。

4.简单实现

#include <stdio.h> #include <stdbool.h> #define MAXSIZE 100 #define ERROR 0 #define OK 1 typedef int Status; typedef int SElemType; typedef struct{ SElemType data[MAXSIZE]; int top; }SqStack; /* 入栈 */ Status push(SqStack* S, SElemType e){ if(S->top == MAXSIZE-1){ return ERROR; } S->data[++S->top] = e; return OK; } /* 出栈 */ Status pop(SqStack* S, SElemType *e){ if(S->top == -1){ return ERROR; } *e = S->data[S->top--]; return OK; } /* 返回栈的个数 */ int StackLength(SqStack* S){ return S->top+1; } /* 判断栈空 */ bool StackEmpty(SqStack* S){ if(S->top == -1) return true; return false; } /* 判断栈满 */ bool StackFull(SqStack* S){ if(S->top == MAXSIZE-1) return true; return false; } /* 拿到栈顶元素 */ Status getTop(SqStack* S, SElemType* e){ if(S->top == -1) return ERROR; *e = S->data[S->top]; return OK; } /* 遍历栈中元素 */ void printStack(SqStack* S){ if(StackEmpty(S)){ printf("栈空！\n"); return; } int i = 0; printf("栈中元素遍历：\n"); while(i<=S->top) printf("%d\n", S->data[i++]); } int main(){ bool continueFlag = true; //是否循环菜单 int functionNum; //功能号 SqStack stack, *S = &stack; S->top = -1; //最开始栈为空 SElemType pushNum, popNum; while(continueFlag){ printf("-----------菜单------------\n"); printf("-----------1.入栈----------\n"); printf("-----------2.出栈----------\n"); printf("-----------3.返回栈顶元素--\n"); printf("-----------4.栈元素遍历----\n"); printf("-----------5.栈元素个数----\n"); printf("-----------6.判断栈是否为空\n"); printf("-----------7.判断栈是否已满\n"); printf("-----------8.退出----------\n"); printf("输入功能号：\n"); scanf("%d",&functionNum); printf("-----------------------\n"); switch(functionNum){ case 1: printf("请输入要入栈的元素：\n"); scanf("%d", &pushNum); if(push(S, pushNum)) printf("入栈成功！\n"); else printf("入栈失败！\n"); break; case 2: if(pop(S, &popNum)) printf("出栈元素：%d\n",popNum); else printf("栈空！\n"); break; case 3: if(getTop(S, &popNum)) printf("栈顶元素：%d！\n",popNum); else printf("栈空！\n"); break; case 4: printStack(S); break; case 5: printf("栈元素个数：%d\n",StackLength(S)); break; case 6: if(StackEmpty(S)) printf("栈空！\n",popNum); else printf("栈非空！\n"); break; case 7: if(StackFull(S)) printf("栈满！\n",popNum); else printf("栈不满！\n"); break; case 8: continueFlag = false; printf("欢迎使用！\n"); break; default: printf("功能号不存在！\n"); break; } printf("-----------------------\n"); } return 0; }