栈的基本概念

栈(Stack)只允许在一端进行插入或者删除操作的线性表

FILO: Firt In Last Out

基本操作

• InitStack(&S):初始化一个空栈
• StackEmpty(S):判断栈是否为空，若栈为空则返回true，否则返回false
• Push(&S,x):进栈，若栈S未满，则将x加入使之成为新栈顶
• Pop(&S,&x):出栈，若栈非空，则弹出栈顶元素，并用x返回
• GetTop(S,&x):读栈顶元素，若栈非空，则用x返回栈顶元素
• ClearStack(&S):销毁栈，并释放S占用的内存空间

顺序栈

采用顺序存储的栈

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;

共享栈

将两个栈底设置在空间的两端，栈顶向空间中间延伸

判空：0号栈top==-1
1号栈top==MaxSize
栈满：top1-top0==1

优点:存取时间复杂度仍为O(1),但空间利用更有效

链式栈

采用链式存储的栈

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
} *LiStack;

所有操作都在表头执行

队列

队列(Queue)只允许在表的一端进行插入，表的另一端进行删除操作的线性表

基本操作

• InitQueue(&Q):初始化一个空栈
• QueueEmpty(Q):判断栈是否为空，若栈为空则返回true，否则返回false
• EnQueue(&Q,x):入队，若队列Q未满，则将x加入使之成为新队尾
• DeQueue(&Q,&x):出队，若队列非空，则删除队头元素，并用x返回
• GetHead(Q,&x):读队头元素，若Q非空，则用x返回队头元素
• ClearQueue(&Q):销毁队列，并释放Q占用的内存空间

顺序队

采用顺序存储的队列

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front;  //  队头元素（队头元素的前一位置）
    int rear;   //队尾元素的下一个位置（指向队尾元素）
}

初始化front==rear==0
队空条件：Q.front == Q.rear
队长：Q.rear-Q.front

循环队列

把存储队列的顺序队列在逻辑上视为一个环

front指针移动：Q.front = (Q.front+1)% MaxSize
rear指针移动:Q.rear = (Q.rear+1)% MaxSize
队列长度：（Q.rear+MaxSize-Q.front）% MaxSize

链队

采用链式存储的队列

typedef struct {
  ElemType data;
  struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

输出序列

应用