操作受限线性表

栈

只允许在一端进行插入或删除操作的线性表
操作与普通顺序表区别不大
特点：先进后出，后进先出

#define MaxSize 10 //定义栈中元素的最大个数

typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶元素
}SqStack;

//初始化栈
void InitStack(SqStack &S){
S.top = -1; //初始化栈顶指针
}

//判栈空
bool StackEmpty(SqStack S){
if(S.top == -1) //栈空
return true;
else //栈不空
return false;
}

//新元素进栈
bool Push(SqStack &S, ElemType x){
if(S.top == MaxSize - 1) //栈满
return false;

S.top = S.top + 1;    //指针先加1
S.data[S.top] = x;    //新元素入栈

/*
S.data[++S.top] = x;
*/
return true;

}

//出栈
bool Pop(SqStack &x, ElemType &x){
if(S.top == -1) //栈空
return false;

x = S.data[S.top];       //先出栈
S.top = S.top - 1;       //栈顶指针减1
return true;

/*
x = S.data[S.top--];
*/

//只是逻辑上的删除，数据依然残留在内存里

}

//读栈顶元素
bool GetTop(SqStack S, ElemType &x){
if(S.top == -1)
return false;

x = S.data[S.top];      //x记录栈顶元素
return true;

}

void testStack(){
SqStack S; //声明一个顺序栈(分配空间)
InitStack(S);
//…
}

与单链表相同
typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}*LiStack; //栈类型的定义

先进先出

只允许从两端插入、两端删除的线性表
输入受限的双端队列：只允许从一端插入、两端删除的线性表
输出受限的双端队列：只允许从两端插入、一端删除的线性表