3.1 栈
栈是限定插入或删除操作只能在表尾进行的线性表；后进先出
顺序栈：类似于顺序表，指向表尾（最后插入的位置）作为栈顶指针
在非空栈中，栈顶指针top并不是指向栈顶元素，而是始终指在栈顶元素的下一个位置上——top指针永远指向下一次要插入的位置
-
base = NULL，说明栈不存在。
-
base = top 作为栈空的标志。
-
top-base 的值为栈的长度。
类型定义
1 #define STACK_ INIT_ SIZE 100 //存储空间初始分配量
2 #define STACKINCREMENT 10 //存储空间分配增量
3
4 顺序栈的类型定义：
5 typedef struct {
6 SElemType *base;
7 SElemType *top; //栈顶指针
8 int stacksize; //当前分配的存储空间，以元素为单位
9 } SqStack ;
初始化
1 Status InitStack (SqStack &S ) // 构造一个空栈S
2 { S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType)); // S.base = new SElemType [STACK_INIT_SIZE];
3 if (! S.base ) exit(OVERFLOW); //存储分配失败
4 S.top =S.base;
5 S.stacksize =STACK_INIT_SIZE;
6 return OK;
7 }
插入元素
1 Status Push (SqStack &S , SElemType e )
2 {
3 if(S.top - S.base >= S.stacksize)
4 { // 当前存储空间已满，增加分配
5 S.base = (SElemType *)realloc(S.base,
6 (S.stacksize+STACKINCREMENT)*sizeof (SElemType));
7 if (! S.base ) exit(OVERFLOW); // 存储分配失败
8 S.top =S.base+S.stacksize;
9 S.stacksize += STACKINCREMENT //新的存储容量
10 }
11 *S.top++=e;
12 return OK;
13 }
删除元素
Status Pop (SqStack &S , SElemType &e )
{ // 若栈空，返回ERROR
if(S.top == S.base ) return ERROR; //若栈不空，删除栈顶元素，用e返回其值并返回OK
e=*--S.top;
return OK;
}
取栈顶元素
Status GetTop(SqStack S , SElemType &e )
{ //若栈空, 返回ERROR
if( S.top ==S.base ) return ERROR; //若栈不空，则用e返回S的栈顶元素，并返回OK，
e=*(S.top-1);
return OK;
}
3.2 队列
队列（queue )是一种先进先出(first in first out，简称FIFO表)的线性表。它只允许在表的一端进行插入元素，而在表的另一端进行删除元素。在队列中，允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。
类型定义
1 typedef struct QNode
2 {QElemType data;
3 struct QNode *next;
4 }QNode, *QueuePtr; //声明结点类型：QNode
5
6 typedef struct
7 { QueuePtr front; // 队头指针
8 QueuePtr rear; // 队尾指针
9 } LinkQueue; //声明链队列类型名： LinkQueue
空的链队列的判决条件：头指针和尾指针均指向头结点
循环队列-顺序表示
假溢出
解决方法：循环队列
类型定义
1 #define MAXQSIZE 100 //最大队列长度
2
3 typedef struct {
4 QElemType *base; //指向初始化的动态分配存储空间
5 int front; //头指针, 若队列不空，指向队头
6 int rear; //尾指针, 若队列不空，指向队尾的下一个位置
7 } SqQueue; //声明顺序队列类型名 SqQueue
8
9 SqQueue Q ; //定义顺序队列变量 Q
队空条件：front==rear
队满条件：(rear+1)%MAXQSIZE == front
如果不少用一个元素空间，则队列满的时候，front == rear 并不能确定队列状态（可空可满）
初始化
1 Status InitQueue ( SqQueue &Q )
2 {// 构造一个空队列Q
3 Q.base =(QElemType *) malloc(MAXQSIZE* sizeof(QElemType));
4 if (!Q.base) exit (OVERFLOW); // 存储分配失败
5 Q.front = Q.rear = 0;
6 return OK;
7 }
队列长度
1 int QueueLength( SqQueue Q )
2 {//返回队列Q的元素个数, 即队列的长度
3 return ( Q.rear-Q.front+MAXQSIZE )%MAXQSIZE;
4 }
插入元素
Status EnQueue (SqQueue &Q, ElemType e)
{// 插入元素e为Q的新的队尾元素
if ((Q.rear+1) % MAXQSIZE == Q.front )return ERROR; //队列满
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}
删除元素
1 Status DeQueue (SqQueue &Q, ElemType &e) {
2 // 若队列不空，则删除Q的队头元素，
3 // 用e返回其值，并返回OK; 否则返回ERROR
4 if (Q.front == Q.rear) return ERROR;
5 e = Q.base[Q.front];
6 Q.front = (Q.front+1) % MAXQSIZE;
7 return OK;
8 }
标签：return,队列,top,base,front,rear From： https://www.cnblogs.com/eecsCodeStar/p/16981334.html