第四章栈与队列

引言：
栈：只能在线性表表尾进行插入和删除的表
队列：只允许在一端进行插入，而在另一端删除的线性表

4.1 顺序栈

最先进站的元素是否只能最后一个出栈？
并不是，因为栈虽然对线性表的插入和删除做了限制，但是并没有对出战时间进行限制。即：当并非所有元素都进栈时，陷进去的元素可以先出栈
eg：1,2,3的出栈顺序可能是1,3,2。1先进栈，立刻出栈，然后2,3进栈。然后出栈。(看，这个1最先进去，不是可以第一个出来吗)
栈的顺序存储结构
（1）站的线性表结构用数组实现。栈只能一端进行操作，那么用哪一端来作为栈顶和栈底呢？选择交表为0的一端作为栈底，因为首元素在栈底，变化最小。
（2）定义一个top变量指示栈顶元素在数组中的位置。
（3）因此，站的顺序结构分为数组和top变量
```
#define MAXSIZE 100
typedef int ElemenType;
typedef struct {  // 数组和top栈顶标记
    ElemenType data[MAXSIZE];
    int top;
}SqStack;
```

站的操作

/**
 * 进栈
 */
int push (SqStack *stack,ElemenType e){
    if(stack->top == MAXSIZE -1)
        return 0;
    int i = ++(stack->top);
    stack->data[i] = e;
    return 1;
}
/**
 * 出栈
 */
int pop(SqStack *stack,ElemenType *e){
    if(stack->top==-1)    // top=-1说明栈空
        return 0;
    *e = stack->data[stack->top];
    stack->top--;
    return  1;
}

两个栈共享空间(存储相同数据类型的元素)
（1）两栈共享空间，就是用一个超大数组来存放2个栈的数据。这样2个栈的大小不固定，只要总和不超过最大数组即可
（2）这两个栈，一个栈的栈底在数组小标为0的地方。另一个栈的栈底在数组下标为n-1的地方。2各站增加元素，就是从这个超大数组的两端进行元素赋值，向中间靠拢，直到2个栈的栈顶相遇
（3）两个栈相遇时top1 + 1 = top2
（4）top1=-1时栈1为空，top2=n时栈2为空(因为栈顶是可以添加元素的位置，top2=n-1还能添加元素)
（5）若栈2为空栈，则栈1满的条件为top1 = n-1。若栈1位空栈，栈2满的条件为top2=0

4.2 链栈

链栈的单链表没有头结点
单链表的头结点便于数据操作，所以通常栈顶规定为第一个节点，因此，链表的头结点失去意义二不复存在，使得链栈的第一个节点即为数据节点，就是栈顶节点
链栈不存在栈满的情况，链栈的栈空条件为top=NULL

链栈的定义

typedef int ElemType;
#define MAXSIZE 1000
typedef struct StackNode{
    ElemType data;
    StackNode next;
}StackNode, *LinkedStackPtr;

typedef struct LinkedStack{
    LinkedStackPtr  top;  // 指向节点的指针，用作栈的top标记
    int count;
}LinkedStack;

栈的push与pop操作

/**
 * 进栈
 */
int push(LinkedStack *stack,ElemType e){
    LinkedStackPtr s = (LinkedStackPtr) malloc(sizeof(StackNode))  ;
    s->data = e;
    s->next = stack->top;
    stack->top = s;
    stack->count++;
    return 1;
}

/**
 * 出栈
 */
int pop(LinkedStack *stack,ElemType *e){
    if(stack->top == NULL)
        return 0;
    *e = stack->top->data;
    LinkedStackPtr  p = stack->top;  // top标记，头指针标记
    stack->top = stack->top->next;
    free(p);  // 释放删除节点的内存
    stack->count --;
    return 1;
}

【注】：链栈的push与pop操作时间复杂度都是O(1)，因为都在头结点操作，链栈中的top就是头指针，指向头结点

4.4 队列的顺序表实现

数组实现队列的逻辑
（1）数组实现队列，下表为0的元素为队头，下标n-1位队尾。
（2）元素出队后，队头标记增加1。为了使出队后，队头前面的数组仍能被使用，就要把后面的全部元素向前移一位，造成大规模的元素复制。这种情况很好理解，正如人们排队买票，第一个人买完票走后，其他所有人都要向前进一步。
（3）因此为了避免大规模的数据复制，采用循环使用数组.
循环使用数组-循环队列
（1）增加2个标记：指向队头元素的front，指向队尾元素下一个位置的rear。当front=rear时，队列满
（2）队列空时，front=rear。队列满时，还是front=rear。如何区分队列控和队列满呢，有两个解决办法：
（a）引入flag标记位。当flag=1时，队列满
（b）让队列空时front=rear,队列满时，修改其条件，保留一个元素空间。即队列满时，数组还有一个空闲单元。
（3）通常，使用第二种办法来区别对空和堆满。此时，堆满的条件就变为了(rear+1)%QueueSize == front。另外，当rear>front时，队列长度为rear-front，当rear<front时，队列分为2个部分，一段长QueueSize-front，另一段长rear。共长rear+QueueSize-front。
整合rear大于和小于front的情况得出：队列长度为(rear-front+QueueSize)%QueueSize。

循环队列的定义与操作

#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
#define MAXSIZE 1000
typedef struct {
    ElemType data[MAXSIZE];
    int front;
    int rear;
}SeqQueue;

/*  队列初始化 */
int initQueue(SeqQueue *queue){
    queue->front = 0;
    queue->rear = 0;
    return 1;
};

/* 队列长度 */
int queueLength(SeqQueue *queue){
    int rear = queue->rear;
    int front = queue->front;
    return (rear - front + MAXSIZE)%MAXSIZE;
}

/*  入队操作 */
int enQueue(SeqQueue *queue,ElemType e){
    if((queue->rear+1) % MAXSIZE == queue->front) // 队满
        return 0;
    queue->data[queue->rear] = e; 
    queue->rear = (queue->rear)%MAXSIZE ;
    return 1;
}

/*  出队操作 */
int deQueue(SeqQueue *queue,ElemType *e){
    if(queue->rear == queue->front)
        return 0;
    * e = queue->data[queue->front];
    queue->front = (queue->front)%MAXSIZE;
    return 1;
}

4.5 队列的链式存储

队列的链式存储，就是只能尾进头出的链表
链式队列同样需要front与rear指标。队列为空时rear==front，不存在队列满的情况

队列的声明与操作

#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
#define MAXSIZE 1000
typedef struct QNode{
    ElemType data;
    QNode *next;
}QNode,*Queueptr;

typedef struct{
    Queueptr front;
    Queueptr rear;
}LinkedQueue;

/* 入队 */
int enQueue(LinkedQueue *queue,ElemType e){
    Queueptr newNode = (Queueptr)malloc(sizeof(QNode));
    if(newNode == NULL)   // 存储空间分配失败
        return 0;
    newNode->data = e;
    newNode->next = NULL;
    queue->rear->next = newNode; //  将这个节点加入链队
    queue->rear = newNode;           //  改变rear指针指向
    return 1;
}

/* 出对 */
int deQueue(LinkedQueue *queue,ElemType *e){
    if(queue->front == queue->rear)
        return 0;
    Queueptr  p = queue->front->next;   // front就是链表头指针,p是将要删除的节点
    *e = p->data;
    queue->front->next = p->next;
    if(queue->rear == p)
        queue->rear = queue->front;
    free(p);
    return 1;
}

循环队列和链队的增加和删除元素的时间复杂度都是O(1)，因为有front和rear指标。当队列的元素个数可以确定的时候，建议用循环队列。否则可以使用链队。

第四章 栈与队列

第四章 栈与队列

4.1 顺序栈

4.2 链栈

4.4 队列的顺序表实现

4.5 队列的链式存储

第四章栈与队列

第四章栈与队列