若没有相关知识基础，可以先看看下面文章哦🤗👇
线性表
栈和队列的基本概念
栈
栈(stack)是只允许在一端进行插入和删除操作的线性表
其最大的特性就是LIFO(last in first out) 后进先出
栈的顺序存储实现
#include<iostream>
using namespace std;
#define maxSize 10//栈的最大容量
typedef struct {
int a[maxSize];
int top;
}sqStack;
//初始化
void initStack(sqStack& s) {
s.top = -1;//栈顶指针的初始化有多种,每种都要注意其栈满的条件
}
//判空
bool empty(sqStack& s) {
if (s.top == -1)return true;
}
//入栈
bool push(sqStack& s, int x) {
//如果maxSize为10,我们的有效存储下标为0~9
if (s.top == maxSize - 1)return false;
s.a[++s.top] = x;//栈顶指针先移动,然后元素入栈
return true;
}
//出栈
bool pop(sqStack& s, int& x) {
if (s.top == -1)return false;//栈空
x = s.a[s.top--];//先出栈,指针再移动
return true;
}
//得到栈顶元素
bool getTop(sqStack s, int& x) {
if (s.top == -1)return false;
x = s.a[s.top];
return true;
}
int main() {
return 0;
}
栈的链式存储实现(不带头结点)
由于栈是特殊的线性表,
我们可以采用头插法建立单链表的形式实现链栈
以下是不带头结点的链栈基本操作,在不带头结点的链栈中，
首结点相当于栈顶
#include<iostream>
using namespace std;
typedef struct linkStack {
int num;
struct linkStack* next;
}stackNode,*linkStack;
void initStack(linkStack& s) {
s = NULL;
}
//判断是否为空
bool isEmpty(linkStack s) {
return s == NULL;
}
//计算栈的长度
int getLen(linkStack s) {
int length = 0;
stackNode* temp = s;
while (temp != NULL) {
length++;
temp = temp->next;
}
return length;
}
//利用单链表的头插法进行链栈的入栈操作
bool push(linkStack& s, int x) {
stackNode* p =(stackNode*)malloc(sizeof(stackNode));
//如果当前栈中没有结点,那么当前节点为首结点
if (isEmpty(s)) {
p = s;
return true;
}
p->num = x;
p->next = s;
s = p;
return true;
}
bool pop(linkStack& s, int& x) {
if (isEmpty(s))return false;
stackNode* p = (stackNode*)malloc(sizeof(stackNode));
x = s->num;//返回弹出的元素
p = s;
s = s->next;
free(p);//删除之前的首结点
return true;
}
int getTop(linkStack s) {
if (isEmpty)return -999;//代表不存在
return s->num;
}
队列
只允许在一端插入,在另一端删除的线性表
其最大特性为先进先出(First in first out)
队列的顺序存储实现
#include <iostream>
using namespace std;
#define maxSize 10
typedef struct {
int num[maxSize];
int front, rear;
}sqQueue;
//初始化队列,规定头指针front==尾指针rear的时候
//为队空状态
void initQueue(sqQueue& q) {
q.rear = q.front = 0;
}
//判断队列是否为空
bool queueEmpty(sqQueue q) {
if (q.rear == q.front)return true;
return false;
}
//入队
bool enQueue(sqQueue& q, int x) {
//判断队列是否存满
if ((q.rear + 1) % maxSize == q.front)return false;
//在尾部插入
q.num[q.rear] = x;
//尾指针自增
q.rear = (q.rear + 1) % maxSize;
return true;
}
//出队
bool deQueue(sqQueue& q, int& x) {
//队列如果为空则无法出队返回false
if (queueEmpty(q))return false;
//将出队的元素带回
x = q.num[q.front];
//对头指针自增
q.front = (q.front + 1) % maxSize;
return true;
}
//读取队头
bool getHead(sqQueue q, int& x) {
//队列为空则返回false
if (queueEmpty(q))return false;
//读取队头元素
x = q.num[q.front];
return true;
}
if ((q.rear + 1) % maxSize == q.front)return false;
- 如何判断队满?
借助于模运算的性质,我们将存储数据的下标映射到0~maxSize-1这样的范围,形成一个环状结构(循环队列)
由于队头指针==队尾指针已经被定义成为判断队列是否为空的条件，所以要换一种形式来定义队列是否已满。 - 这里我们通过牺牲一个存储单元的形式来判断是否存满
队列的链式存储实现(带头结点)
链式队列的特性就类似于在单链表的表头进行删除,表尾进行插入的操作
//链队每个结点的类型
typedef struct linkNode {
int data;
struct linkNode* next;
}linkNode;
//链队的头尾指针
//头指针相当于队头,尾指针相当于队尾
typedef struct {
linkNode* front;
linkNode* rear;
}linkQueue;
//初始化链队
void initQueue(linkQueue& q) {
//初始化头尾指针
q.front = q.rear = (linkNode*)malloc(sizeof(linkNode));
q.front->next = NULL;
}
//判断是否为空
bool isEmpty(linkQueue q) {
if (q.front == q.rear)return true;
else return false;
}
//入队
void enQueue(linkQueue& q, int x) {
//定义新结点
linkNode* s = (linkNode*)malloc(sizeof(linkNode));
s->data = x;
//由于入队操作是在队尾,且当前元素入队之后一定是最后一个元素
//所以其指向为NULL
s->next = NULL;
//之前的队尾指向新的队尾
q.rear->next = s;
//之前的队尾指针变为新的队尾
q.rear = s;
}
//出队
bool deQueue(linkQueue& q, int& x) {
//队空则出队失败
if (isEmpty(q))return false;
//让p指向出队结点,即头指针的next
linkNode* p = q.front->next;
//将元素记录
x = p->data;
//删除
q.front->next = p->next;
//如果被删除的元素是队列中最后一个元素
//那么需要修改队尾指针指向
if (q.rear == p)q.rear = q.front;
//释放节点
free(p);
return true;
}
//获取队头
int getTop(linkQueue q){
if (isEmpty(q))return -9999;//代表不存在
return q.front->data;
}
入队图解
出队图解
总结
栈和队列都是一种操作受限的线性表，
栈只能在栈顶插入，删除。
其特点就是先进后出，类似于压子弹入匣的过程
而队列只能在队头删除，队尾删除。
其特点是先进先出。
🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻
🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹
😇 本篇文章存在多处不足，如有修改意见，可以私信或者评论哦，还望海涵 😇
本篇文章部分内容来自于 王道-数据结构