目录
知识框架
栈
栈的基本概念
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。 栈中的数据元素遵守后进先出 LIFO （ Last In First Out ）的原则。
栈的操作
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。出栈：栈的删除操作叫做出栈。 出数据也在栈顶 。
手撕栈
对于栈的实现我们是要用链表好还是数组好呢？
使用数组：
优点：数据连续存储在栈区，比堆区不连续存储要缓存友好，显然速度也更快；另外数组一般属于高级语言语法中的基本类型，结构简单，有利于编译器做寄存器优化、常量折叠、无用代码精简等，优化完速度还要更快。
缺点：数组大小在编译期写死 (C99 有了可变数组，但实际上 VC 也并未支持，C++ 亦未能兼容这一特性)，数组开多大你就只能存多少数据，超了就是越界；另栈区空间宝贵，利用数组结构实现的栈能存的数据显然没有利用链表结构能存的那么多。所以注定了数组封装的栈根本就不能应用于工程实践。
使用链表：优点缺点恰好就是以上反过来说。
实际工程中的方案：C++ STL (可以说是算法 & 数据结构模板库中的标杆) 默认采用的是用双端队列来封装栈。双端队列底层由多块不连续的缓冲区组成，但各个缓冲区内部元素连续。这样可以减少内存分配次数，降低内存碎片，提高缓存命中率，可以说综合了数组和链表的优点。
我们这边使用的场景比较简单所以我们先用数组来实现栈，在后面也会提到如何使用队列来封装栈，由浅入深。
栈初始化
typedef int STDataType;
struct Stack
{
STDataType* p;
int top;
int capacity;
};
//初始化栈
void StackInit(Stack* ps)
{
ps->p = (STDataType*)malloc(sizeof(Stack));
ps->top = 0;
ps->capacity = 4;
}
插入
一进来我们先判断空间是否足够，如果不够那么我们需要开辟空间
// 入栈
void StackPush(Stack* ps, STDataType data)
{
if (ps->capacity == ps->top)
{
//增容
Stack* tmp = realloc(ps->p, sizeof(Stack) * ps->capacity * 2);
if (tmp == NULL)
{
perror("ERROR:");
exit(-1);
}
ps->p = tmp;
tmp = NULL;
ps->capacity *= 2;
}
ps->p[ps->top] = data;
ps->top++;
}
出栈
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}获取栈顶元素
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->p[ps->top - 1];
}判断栈是否为空
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
return ps->top == 0;
//空返回1；非空返会0；
}获取栈的有效元素个数
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
return ps->top;
}销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->p);
ps->p = NULL;
ps->top = 0;
ps->capacity = 0;
}完整代码
Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
struct Stack
{
STDataType* p;
int top;
int capacity;
};
typedef struct Stack Stack;
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);Stack.c
#include "stack.h"
//初始化栈
void StackInit(Stack* ps)
{
ps->p = (STDataType*)malloc(sizeof(Stack));
ps->top = 0;
ps->capacity = 4;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
if (ps->capacity == ps->top)
{
//增容
Stack* tmp = realloc(ps->p, sizeof(Stack) * ps->capacity * 2);
if (tmp == NULL)
{
perror("ERROR:");
exit(-1);
}
ps->p = tmp;
tmp = NULL;
ps->capacity *= 2;
}
ps->p[ps->top] = data;
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->p[ps->top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
return ps->top == 0;
//空返回1；非空返会0；
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->p);
ps->p = NULL;
ps->top = 0;
ps->capacity = 0;
}test.c
#include"stack.h"
void test()
{
Stack ps;
StackInit(&ps);
StackPush(&ps, 1);
StackPush(&ps, 2);
printf("%d\n", StackTop(&ps));
StackPop(&ps);
StackPush(&ps, 3);
StackPush(&ps, 4);
printf("%d\n", StackTop(&ps));
printf("%d\n", StackTop(&ps));
printf("%d\n", StackTop(&ps));
printf("%d\n", StackTop(&ps));
while (!StackEmpty(&ps))
{
printf("%d ",StackTop(&ps));
StackPop(&ps);
}
StackDestroy(&ps);
}
int main()
{
test();
return 0;
}测试结果
队列
队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)入队列：进行插入操作的一端称为 队尾出队列：进行删除操作的一端称为 队头
对于队列来说一种入队顺序，只有一种出队顺序！！！
队列常见的操作
队列的初始化：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);
判断队列是否为空：bool QueueEmpty(Queue* pq);
队列的元素个数：int QueueSize(Queue* pq);
队列的顺序存储结构
#define MAXSIZE 100 //定义队列中元素的最大个数
typedef struct
{
ElemType data[MAXSIZE]; //存放队列元素
int front;
int rear;
}SqQueue;
初始状态（队空条件）：Q->front == Q->rear == 0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。
如果我们的队列长度固定，又想要有较高的性能，那么就可以用顺序表示方式的队列
队列的假溢出现象
顺序队列假溢出就是，随着队头出队慢慢地就会空出一个个存储单元，但是队尾一直再进，最后就是存储空间根本没用满，队列就满了！解决办法2个，1个是空出1个存储单元出来，另一个是做成循环队列。
此时的e就是假溢出，实际上还有空间，为充分利用向量空间，克服"假溢出"现象的方法是：
循环队列
循环队列的概念：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。
队列判空的条件是front=rear，
而队列判满的条件是front=（rear+1)%MaxSize。
循环队列的实现
typedef struct MyCircularQueue
{
int* arr;
int head; //分别指向队列的头尾
int tail;
int k; //存储k值
} MyCircularQueue;
初始化
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* queue = malloc(sizeof(MyCircularQueue));
queue->arr = (int*)malloc(sizeof(int) * (k + 1)); // "k + 1!"
queue->head = queue->tail = 0;
queue->k = k;
return queue;
}
判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
assert(obj);
return obj->head == obj->tail;
}
判断循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->head == 0 && obj->tail == obj->k) ||
(obj->tail + 1 == obj->head);
}
入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
assert(obj);
if (myCircularQueueIsFull(obj))
{
return false;
}
obj->arr[obj->tail] = value;
if (obj->tail == obj->k)
obj->tail = 0;
else
obj->tail += 1;
return true;
}
出队列
int myCircularQueuePop(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
{
return ; //队列空的判断
}
int ret=obj->arr[obj->head]; //将队头元素赋值给e
obj->head = (obj->head + 1) % obj->k;
return ret;//front指针向后移一位置，若到最后则转到数组头部
}
删除元素。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj))
return false;
if (obj->head == obj->k)
obj->head = 0;
else
obj->head++;
return true;
}
取队头数据
int myCircularQueueFront(MyCircularQueue* obj)
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[obj->head];
}
取尾数据
int myCircularQueueRear(MyCircularQueue* obj)
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;
if (obj->tail == 0)
return obj->arr[obj->k];
return obj->arr[obj->tail - 1];
}
打印队列
void myCircularQueueprint(MyCircularQueue* obj)
{
while (!myCircularQueueIsEmpty(obj))
{
printf("%d ",myCircularQueuePop(obj) );
}
}
销毁队列
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->arr);
free(obj);
}
运行结果
int main()
{
int a = 10;
MyCircularQueue* Q=myCircularQueueCreate(a);
myCircularQueueEnQueue(Q, 1);
myCircularQueueEnQueue(Q, 2);
myCircularQueueEnQueue(Q, 3);
myCircularQueueEnQueue(Q, 4);
myCircularQueueEnQueue(Q, 5);
myCircularQueuePop(Q);
myCircularQueueEnQueue(Q, 5);
myCircularQueueEnQueue(Q, 6);
myCircularQueueEnQueue(Q, 7);
myCircularQueueEnQueue(Q, 8);
myCircularQueueprint(Q);
return 0;
}
队列结构的选择
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数
组头上出数据，效率会比较低。那么接下来我们就讲讲队列的链式存储
队列的链式存储结构
队列的链式结构就是一个链表，但是他只能从尾部插入数据，从头部出数据，为了方便得知队列的有效元素个数，我们可以用一个整形size来记录
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
队列的实现
队列的初始化：void QueueInit(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
队列的销毁：void QueueDestroy(Queue* pq);
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}
入队：void QueuePush(Queue* pq, QDataType x);
如果开辟空间失败的话，直接退出，如果成功的话，则将值存入节点，接下来我们还需要判断是否是第一次插入，因为我们没有设置头节点，如果是首次插入，则tail为空，那么head和tail都是指向这第一个节点的否则只需要改变tail即可。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
出队：void QueuePop(Queue* pq);
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
获取队头元素：QDataType QueueFront(Queue* pq);
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
获取队尾元素：QDataType QueueBack(Queue* pq);
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
判断队列是否为空：bool QueueEmpty(Queue* pq);
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
队列的元素个数：int QueueSize(Queue* pq);
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}完整代码
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
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);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
assert(pq);
/*QNode* cur = pq->head;
int n = 0;
while (cur)
{
++n;
cur = cur->next;
}
return n;*/
return pq->size;
}#include <stdio.h>
#include "Queue.h"
// 解耦 -- 低耦合 高内聚
// 数据结构建议不要直接访问结构数据，一定要通过函数接口访问
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
printf("%d ", QueueFront(&q));
QueuePop(&q);
printf("%d ", QueueFront(&q));
QueuePop(&q);
QueuePush(&q, 4);
QueuePush(&q, 4);
QueuePush(&q, 4);
printf("Size:%d\n", QueueSize(&q));
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
//TestStack();
TestQueue();
return 0;
}运行结果
双端队列
双端队列的概念
deque （double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。
以上就是栈和队列的基本内容了，希望大家多多支持
本文含有隐藏内容，请 开通VIP 后查看