数据结构 -- 栈和队列
1.栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
1.2栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
下面是实现顺序栈用的头文件
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
1.先在.h中定义一个结构体
下面是初始化 top = 0 或者 top = -1 的含义，top是下标，栈顶是指你进数据的方向
2. 栈的初始化
3. 栈的销毁
4. 入栈
5. 出栈
6. 获取栈顶元素
7. 获取栈中有效元素个数
8. 检测栈是否为空，top等于0就是空返回true,不等于0返回false
9.测试代码
10.下面是实现顺序栈的完整代码
Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //栈顶
int capacity; //容量
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
// 出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
// 获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空，top等于0就是空返回true,不等于0返回false
bool STEmpty(ST* ps);
Stack.c
#include "Stack.h"
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{
assert(ps);
//满了，扩容
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->a = tmp; //扩完容之后，把新扩容的空间tmp给a
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
// 出栈
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps)); //栈不为空
ps->top--;
}
//获取栈顶元素
STDataType STTop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps)); //栈不为空
return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top; //top是下标，最后一个元素下一个位置。
}
// 检测栈是否为空，top等于0就是空返回true,不等于0返回false
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
test.c
#include"Stack.h"
int main()
{
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
int top = STTop(&s); //获得栈顶元素
printf("%d ", top);
STPop(&s);
STPush(&s, 4);
STPush(&s, 5);
while (!STEmpty(&s)) //栈不为空
{
int top = STTop(&s); //获得栈顶元素
printf("%d ", top);
STPop(&s);
}
STDestroy(&s);
return 0;
}
上述代码运行结果如下：
2.队列
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.2队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
下面是实现链式结构：表示队列用的头文件
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
1.先在.h中定义一个结构体
2.初始化队列
3.销毁队列
4.队尾入队列
5.队头出队列
6.获取队列头部元素
7.获取队列队尾元素
8.获取队列中有效元素个数
9.判断队列是否为空
10.测试代码
11.下面是用链式结构实现队列的完整代码
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDataType;
typedef struct QueueNode
{
int val;
struct QueueNode* next;
}QNode;
入队列
//void QueuePush(QNode** pphead, QNode** pptail);
出队列
//void QueuePop(QNode** pphead, QNode** pptail);
//指向结构体的核心成员，如果只有一个，那就直接传，如果有多个就把它们放进结构体
//封装在结构体里面,形参就不需要二级指针，要想改变结构体成员变量的值
//实参直接把结构体变量的地址传给形参即可
typedef struct Queue
{
QNode* phead; //头指针
QNode* ptail; //尾指针方便找尾
int size; //有效元素个数
}Queue;
// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
Queue.c
#include "Queue.h"
// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail) //队列不为空
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
else //队列为空
{
pq->phead = pq->ptail = newnode;
}
pq->size++;
}
//出队列
void QueuePop(Queue* pq)
{
assert(pq);
//0个节点，也就是phead为空
//温柔检查
//if (pq->phead == NULL)
// return;
//暴力检查
assert(pq->phead != NULL);
//一个节点
if (pq->phead->next == NULL)
{
free(pq->phead); //两个指针指向同一个节点，只要free一个指针就行
pq->phead = pq->ptail = NULL;
}
else //多个节点
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
//暴力检查,链表不能为空
assert(pq->phead != NULL);
return pq->phead->val;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
// 暴力检查 ,链表不能为空
assert(pq->ptail != NULL);
return pq->ptail->val;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
test.c
#include "Queue.h"
int main()
{
Queue q;
QueueInit(&q); //初始化队列
QueuePush(&q, 1); //入队列
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
while (!QueueEmpty(&q)) //判断队列是否为空
{
printf("%d ", QueueFront(&q)); //获得队列头部元素
QueuePop(&q);
}
QueueDestroy(&q); //销毁队列
return 0;
}
上述代码运行结果如下：
另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
3.栈和队列面试题
4.概念选择题
选择题
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是(B)
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（D ）
A 1
B 2
C 99
D 0或者100
4.以下( B)不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(B)(假设队头不存放数据)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)
完