栈

定义

#include <stdio.h>/*
栈只允许在栈顶插入删除操作的线性表Last Insert First Out.
*/// 顺序栈#define MaxSize 10typedef struct 
{int data[MaxSize];  // 静态数组存放栈元素int top;  // 栈顶指针
} SqStack;

栈顶指针指向栈顶元素的栈空为-1

// 栈顶指针指向栈顶元素 空为-1void InitStack1(SqStack &S)
{S.top = -1;  // 栈空
}void Push1(SqStack &S, int x)
{S.data[++S.top] = x;
}int  Pop1(SqStack &S)
{   int x;x = S.data[S.top--];return x;
}int GetTop1(SqStack S)
{return S.data[S.top];
}

测试

int main()
{SqStack S;InitStack1(S);for(int i=1; i<=5; i++){Push1(S, i);}puts("after push...");show1(S);puts("pop....");while( S.top != -1){int x = Pop1(S);printf("%i\n", x);}return 0;
}void show1(SqStack S)
{for(int i=S.top; i!=-1; i--){printf("| %i |\n", S.data[i]);puts("-----\n");}}

栈顶指针指向下一个元素存放位置的栈空为 0

// 栈顶指针指向下一个元素存放位置 空为 0void InitStack0(SqStack &S)
{S.top = 0;  // 栈空
}void Push0(SqStack &S, int x)
{S.data[S.top++] = x;
}void Pop0(SqStack &S)
{int x;x = S.data[--S.top];
}int GetTop0(SqStack S)
{int x;x = S.data[S.top - 1];return x;
}

共享栈

// 共享栈
typedef struct
{int data[MaxSize];int topa;  // 栈a 以下方为栈底 的栈顶指针int topb;  // 栈b 以上方位栈底 的栈顶指针
}ShStack;void InitShStack(ShStack &S)
{S.topa = -1;S.topb = MaxSize;
}bool isFull(ShStack S)  // 栈是否已满
{return S.topa + 1 == S.topb;
}bool Pusha(ShStack &S, int x)
{if(isFull(S) == true){return false;}S.data[++S.topa] = x;return true;
}bool Pushb(ShStack &S, int x)
{if(isFull(S) == true){return false;}S.data[++S.topb] = x;return true;
}int Popa(ShStack &S)
{return S.data[S.topa--];
}int Popb(ShStack &S)
{return S.data[S.topb--];
}