数据结构-栈和队列
总第117篇
前言
本章节开始数据结构第二篇，栈和队列：
栈：
- 栈的存储结构
- 栈的基本操作
队列：
- 队列的存储结构
- 队列的基本操作
前文回顾：数据结构—线性表
栈
我们把类似于弹夹那种先进后出的数据结构称为栈，栈是限定仅在表尾进行插入和删除操作的线性表，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈，栈又称后进后出的线性表，简称LIFO结构。
栈首先是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系，只不过它是一种特殊的线性表而已。
栈的特殊之处在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫做进栈；栈的删除操作叫做出栈。
1.栈的存储结构
用来存放栈的数据元素对应的数据存储结构称为栈的存储结构。
1.1栈的顺序存储结构
栈是线性表的特例，所以栈的顺序存储结构其实就是线性表顺序存储结构的简称，我们简称为顺序栈。线性表是用数组来实现的，对于栈这种只能一头插入删除的线性表来说，用数组下标为0（栈底不变，只需要跟踪栈顶的变化即可）的一端作为栈底比较合适。
顺序栈定义如下：
typedef struct
{
int data[maxsize]; //定义一个数组大小为maxsize的数组，用来存放栈中数据元素
int top; //栈顶指针
}SqStack; //顺序栈定义1.2栈的链式存储结构
把栈顶放在单链表的头部，用链表来存储栈的的数据结构称为链栈。
链栈结点定义如下：
typedef struct LNode
{
int data; //数据域
struct LNode *next; //指针域
}LNode; //链栈结点2.栈的操作
2.1顺序栈的操作
对于顺序栈，一共有4个要素，包括两个特殊状态和两个操作。
特殊状态：
1）栈空状态：st.top == -1,也有的用st.top = 0表示栈空，这个时候栈顶位置为0。
2）栈满状态：st.top == maxsize-1表示栈满。maxsize为栈中最大元素个数，maxsize-1为栈满时栈顶元素在数组中的位置，因数组位置是从0开始的。
操作： 顺序栈的进栈和出栈操作都是在栈顶进行的，所以只需要更改栈顶位置即可达到进栈和出栈的目的。
1)初始化栈：
void initStack(SqStack &st) //初始化栈
{
st.top = -1; //栈顶指针设置为-1
}2)进栈操作：
int push(SqStack &st,int x)
{
if(st.top == maxsize-1) //判断栈是否满，如果满，则不能进栈
return 0;
++(st.top); //栈顶指针位置加1
st.data[st.top] = x //x进栈，放在st.top位置
return 1;
}3)出栈操作： 出栈与进栈是相对应的操作
int push(SqStack &st,int x)
{
if(st.top == -1) //判断栈是否为空，如果空，则不能进行出栈
return 0;
x = st.data[st.top] //先把栈顶元素取出来
--(st.top); //栈顶指针位置减1
return 1;
}4)简化版的操作：
/*初始化栈*/
int stack[maxsize];
int top = -1;
/*元素x进栈*/
stack[++top] = x
/*元素x出栈*/
x = stack[top--]
/*注意++top和top++的区别*/
top = 1
a = ++top
b = top++
a = 2
b = 12.2链栈的操作
与顺序栈对应，链栈也有4个元素，包括两个状态和两个操作。
状态：
1）栈空：lst -> next == NULL,即栈没有后继结点时，栈为空。
2）栈满：如果存储空间无限大的话，不会存在栈满的情况。
操作： 链栈的进栈就是头插法建立链表的插入操作；出栈就是单链表的删除操作。
链栈的插入操作
栈的删除操作 1)链栈初始化：
void initStack(LNode *&lst)
{
lst = (LNode*)malloc(sizeof(LNode)); //制造一个头结点
lst -> next = NULL; //初始头结点指向为NULL
}2)进栈：
void push(LNode *lst,int x)
{
LNode *p;
p = (LNode*)malloc(sizeof(LNode)); //为进栈元素申请结点空间
p -> next =NULL; //初始化结点不指向任何元素
/*进栈,相当于链表的头插法*/
p -> data = x; //将x赋值给p结点的值域
p -> next = lst -> next; //p指针指向原lst指向的结点
lst -> next = p; //lst指向结点p
}3)出栈：
int pop(LNode *lst,int &x)
{
LNode *p;
if(lst -> next == NULL) //栈空则不能出栈，返回0；而栈不会满，所以在进栈的时候未作判断
return 0;
/*出栈，相当于链表的删除结点*/
p = lst -> next;
x = p -> data;
lst -> next = p -> next;
free(p);
return 1;
}4)简化版操作：
/*元素（指针p所指）进栈操作*/
/*类似于头插法建立链表*/
p -> next = lst -> next; //将空栈的头结点指向p
lst -> next = p; //将指针p指向空栈头结点
/*出栈操作（出栈元素保存在x中）*/
/*类似于单链表的删除操作*/
p = lst -> next;
x = p -> data;
lst -> next = p -> next;
free(p);队列：
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，队列是一种先进先出的线性表，简称FIFO，允许插入的一端称为队尾（Rear），允许删除的一端称为队头(Front)。向队中插入元素称为进队，新元素进队后成为新的队尾元素；向队中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。
1.队列的存储结构
用来存储队列数据元素的数据结构。
1.1队列的顺序存储结构：
使用顺序表存储队列时，队列元素的出队是在队头，即下标为0的地方，当有元素出队时，出队元素后面的所有元素都需要向前移动，保证队列的队头始终处在下标为0的位置，此时会大大增加时间复杂度。
用顺序表来存储队列元素的数据结构称为队列的顺序存储结构，定义如下：
typedef struct
{
int data[maxsize]; //定义数组
int front; //队首指针
int rear; //队尾指针
}SqQuene; //顺序队列定义1.2队列的链式存储结构：
用链表来存储队列元素的数据结构称为队列的链式存储结构，定义如下：
队列结点类型定义：
typedef struct QNode
{
int data; //数据域
struct QNode *next; //指针域
}QNode; //队结点类型定义链队类型定义：
typedef struct
{
QNode *front; //队头指针
QNode *rear; //队尾指针
}LiQuene; //链队类型定义2.队列操作
2.1循环队列
因为顺序队列出队时时间复杂度较高，有问题总是要解决的，为什么一定要让队头出现在下标为0的位置呢？所以有人提出了不去限制队列元素必须存储在数组的前n个单元这一条件，这样队头元素就不需要一定在下标为0的位置。但是随着队列元素的出队，队头指针在向后移动，假设队尾指针已经在maxsize-1的位置，这个时候虽然队列还有存储空间，但是队尾已经无法进队了，比如下图这样：
虽然下标为0和1的位置处还有空间，但是队尾已经无法再有新元素进队，我们把这种情况称为“假溢出”，为了解决这种假溢出的问题，就提出了循环队列的概念，让队列的头尾进行相连，这种头尾相连的顺序存储结构称为循环队列。
循环队列需要损失一定的空白，这样只有在队空的时候才会出现front=rear。
循环队列的要素：
两个状态： 队空状态：
qu.rear = qu.front
队满状态：
（qu.rear+1）%maxsize == qu.front
两个操作： 元素x进队操作（移动队尾指针）
qu.rear = (qu.rear+1)%maxSize;
qu.data[qu.rear] = x;元素x出队操作（移动队头指针）
qu.front = (qu.front+1)%maxSize;
x = qu.data[qu.front];初始化队列算法：
void initQueue(SqQueue &qu)
{
qu.front = qu.rear = 0;队首和队尾指针重合，并且指向0
}进队算法：
int enQueue(SqQueue &qu,int x)
{
if ((qu.rear + 1) % maxSize == qu.front) //队满的判断条件，如果队满则不能进队，返回0
return 0;
qu.rear = (qu.reat+1)%maxSize; //若队不满，先移动队尾指针
qu.data[qu.rear] = x; //元素x进队
return 1;
}出队算法：
int enQueue(SqQueue &qu,int &x)
{
if (qu.rear == qu.front) //队空的判断条件，如果队空则不能出队，返回0
return 0;
qu.front = (qu.front+1)%maxSize; //若队不空，先移动队首指针
x = qu.data[qu.front] ; //元素x出队
return 1;
}2.2链队：
链队就是采用链式存储结构存储队列。链队的四个要素：队空和队满，元素进队和出队操作。
队空状态：
lqu -> rear == NULL; or lqu -> front == NULL队满状态： 一般来说不存在队满的情况，只要内存足够大。
元素进队操作(指针p指向进队元素)
lqu -> rear -> next = p;
lqu -> rear = p;元素出队操作（x存储出队元素）
p = lqu -> front;
lqu -> front = p -> next;
x = p -> data;
free(p);初始化链队算法
void initQueue(LiQuene *&lqu)
{
lqu = (LiQueue*)malloc(sizeof(LiQueue));
lqu -> front = lqu -> rear = NULL;
}判断队空算法
int isQueueEmpty(LiQueue *lqu)
{
if(lqu -> rear == NULL || lqu -> front == NULL)
return 1;
else
return 0;
}入队算法
void enQueue(LiQueue *lqu,int x)
{
QNode *p;
p = (QNode*)malloc(sizeof(QNode));
p -> data = x;
p -> next =NULL;
if(lqu -> rear == NULL)
lqu -> front = lqu -> rear = p; //如果队列为空，则新结点既是队尾结点也是队首结点
else
{
lqu -> rear -> next = p; //将新结点链接到队尾，rear指向该结点
lqu -> rear = p;
}
}出队算法
int deQueue(LiQueue *lqu,int &x)
{
QNode *p;
if(lqu -> rear == NULL) //判断队空，如果为空，则不能出队
return 0;
else
p = lqu -> front;
if(lqu -> front == lqu -> rear) //队列中只有一个结点时的出队操作
lqu -> front = lqu -> rear =NULL
else
lqu -> front = lqu -> front -> next;
x = p -> data;
free(q);
return 1;
}