c语言算法链表数据结构--栈，队列

前言

这篇文章主要是关于栈与队列，为什么一般都是将栈与队列挨着讲，因为他们两个像一对欢喜冤家一样，在争锋相对的同时也互相成就，彼此通过不同的性质又可以联系在一起。本章节主要成分部分：什么是栈和队列，栈和队列的构造，栈和队列的习题。通过基础知识完成练习，通过练习巩固知识与理解栈与队列的联系。相信这篇文章会对大家有帮助，因为计算机就是解决我们生活中的问题，栈与队列的性质也是来源于生活中，比如栈--手枪的弹夹，队列--排队。

前言

栈

栈的概念及结构

栈的实现

实现代码

队列

队列的概念及结构

队列的实现

实现代码

循环队列

栈和队列面试题

括号匹配问题---链接

用队列实现栈--链接

用栈实现队列--链接

设计循环队列--链接

栈

栈的概念及结构

栈：

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

动态演示

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

动态演示

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为压栈与出栈正好满足数组的尾插与头删。数组的代价是及小的，操作相当于链表也更加简便。

动态演示

压栈

出栈

实现代码

主要步骤：

构建栈结构--数组，容量，栈顶

接口的实现--初始化栈，入栈，出栈，获取栈顶元素，获取栈中有效元素个数，检测栈是否为空，销毁栈

主函数演示

Stack.h

#define _CRT_SECURE_NO_WARNINGS

#pragma once

#include

typedef int STDataType;

//#define N 10

//typedef struct Stack

//{

// STDataType _a[N];

// int _top; // 栈顶

//}Stack;

// 支持动态增长的栈

typedef int STDataType;

typedef struct Stack

{

STDataType* _a;

int _top; // 栈顶

int _capacity; // 容量

}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

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

// 初始化栈

void StackInit(Stack* ps)

{

assert(ps);//断言传入地址是否为空

ps->_a = NULL;

ps->_capacity = ps->_top = 0;

}

// 入栈

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

if (ps->_top == ps->_capacity)

{

int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity*2;//判断容量是否为空并设置增加容量数量

STDataType* temp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));//增加容量

if (temp == NULL)//判断地址是否开辟成功

{

perror("realloc fail");

exit(-1);

}

ps->_a = temp;//赋址与结构体中

ps->_capacity = newCapacity;//更新容量

}

ps->_a[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->_a[ps->_top-1];

}

// 获取栈中有效元素个数

int StackSize(Stack* ps)

{

assert(ps);

return ps->_top;

}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0

bool StackEmpty(Stack* ps)

{

assert(ps);

return ps->_top==0;

}

// 销毁栈

void StackDestroy(Stack* ps)

{

assert(ps);

free(ps->_a);//清除数组地址

ps->_a = NULL;

ps->_top = ps->_capacity = 0;

}

Test.c

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

//进栈--出栈演示

void TestStack()

{

Stack ps;

StackInit(&ps);

StackPush(&ps,5);

StackPush(&ps,6);

StackPush(&ps,7);

// printf("%d ", StackTop(&ps));

StackPop(&ps);

// printf("%d ", StackTop(&ps));

StackPop(&ps);

while (!StackEmpty(&ps))

{

printf("%d ", StackTop(&ps));

StackPop(&ps);

}

printf("\n");

}

int main()

{

TestStack();

return 0;

}

队列

队列的概念及结构

队列：

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

动态演示

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

动态演示

实现代码

实现步骤：

构建链式结构--结构体指针，数据

构建队列结构--头指针，尾指针

接口的实现--初始化队列，队尾入队列，队头出队列，获取队列头部元素，获取队列队尾元素，获取队列中有效元素个数，检测队列是否为空，销毁队列。

主函数演示

Queue.h

#include

// 链式结构：表示队列

typedef int QDataType;

typedef struct QListNode

{

struct QListNode* _next;

QDataType _data;

}QNode;

// 队列的结构

typedef struct Queue

{

QNode* _front;

QNode* _rear;

QDataType _size;

}Queue;

// 初始化队列

void QueueInit(Queue* q);

// 队尾入队列

void QueuePush(Queue* q, QDataType data);

// 队头出队列

void QueuePop(Queue* q);

// 获取队列头部元素

QDataType QueueFront(Queue* q);

// 获取队列队尾元素

QDataType QueueBack(Queue* q);

// 获取队列中有效元素个数

int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

bool QueueEmpty(Queue* q);

// 销毁队列

void QueueDestroy(Queue* q);

Queue.c

#include "Queue.h"

// 初始化队列

void QueueInit(Queue* q)

{

assert(q);

q->_front = q->_rear = NULL;

q->_size = 0;

}

// 队尾入队列

void QueuePush(Queue* q, QDataType data)

{

assert(q);

QNode* cur = (QNode*)malloc(sizeof(QNode));

if (cur == NULL)

{

perror("malloc fail");

exit(-1);

}

else

{

cur->_data = data;

cur->_next = NULL;

}

if (q->_rear == NULL)

{

q->_front = q->_rear = cur;

}

else

{

q->_rear->_next = cur;

q->_rear = cur;

}

q->_size++;

}

// 队头出队列

void QueuePop(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));

if (q->_front->_next==NULL)

{

free(q->_front);

q->_front = q->_rear = NULL;

}

else

{

QNode* cur = q->_front;

q->_front = q->_front->_next;

free(cur);

cur = NULL;

}

q->_size--;

}

// 获取队列头部元素

QDataType QueueFront(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));

return q->_front->_data;

}

// 获取队列队尾元素

QDataType QueueBack(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));

return q->_rear->_data;

}

// 获取队列中有效元素个数

int QueueSize(Queue* q)

{

assert(q);

return q->_size;

}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

bool QueueEmpty(Queue* q)

{

assert(q);

return q->_front == NULL && q->_rear == NULL;

}

// 销毁队列

void QueueDestroy(Queue* q)

{

assert(q);

QNode* cur = q->_front;

while (cur)

{

QNode* del = cur;

cur = cur->_next;

free(del);

del = NULL;

}

q->_front = q->_rear = NULL;

}

Test.c

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

void TestQueue()

{

Queue q;

QueueInit(&q);

QueuePush(&q, 1);

QueuePush(&q, 3);

QueuePush(&q, 4);

QueuePop(&q);

printf("%d ", QueueFront(&q));

// printf("%d ", QueueBack(&q));

QueuePush(&q, 7);

printf("%d ", QueueBack(&q));

QueuePush(&q, 8);

printf("%d ", QueueBack(&q));

QueuePush(&q, 9);

QueuePush(&q, 10);

QueuePush(&q, 11);

while (!QueueEmpty(&q))

{

printf("%d ", QueueFront(&q));

QueuePop(&q);

}

QueueDestroy(&q);

}

int main()

{

TestQueue();

return 0;

}

循环队列

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

栈和队列面试题

括号匹配问题---链接

动态演示

两种特殊错误情况

实现代码

typedef char STDataType;

typedef struct Stack

{

STDataType* _a;

int _top; // 栈顶

int _capacity; // 容量

}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);

// 初始化栈

void StackInit(Stack* ps)

{

assert(ps);//断言传入地址是否为空

ps->_a = NULL;

ps->_capacity = ps->_top = 0;

}

// 入栈

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

if (ps->_top == ps->_capacity)

{

int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity*2;//判断容量是否为空并设置增加容量数量

STDataType* temp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));//增加容量

if (temp == NULL)//判断地址是否开辟成功

{

perror("realloc fail");

exit(-1);

}

ps->_a = temp;//赋址与结构体中

ps->_capacity = newCapacity;//更新容量

}

ps->_a[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->_a[ps->_top-1];

}

// 获取栈中有效元素个数

int StackSize(Stack* ps)

{

assert(ps);

return ps->_top;

}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0

bool StackEmpty(Stack* ps)

{

assert(ps);

return ps->_top==0;

}

// 销毁栈

void StackDestroy(Stack* ps)

{

assert(ps);

free(ps->_a);//清除数组地址

ps->_a = NULL;

ps->_top = ps->_capacity = 0;

}

bool isValid(char * s){

Stack st;

StackInit(&st);

while(*s)

{

if(*s=='('||*s=='{'||*s=='[')

{

StackPush(&st,*s);

}

else

{

if(StackEmpty(&st))

{

StackDestroy(&st);

return false;

}

char tem= StackTop(&st);

StackPop(&st);

if(*s=='}' && tem!='{' || *s==')' && tem!='(' || *s==']' && tem!='[')

{

StackDestroy(&st);

return false;

}

s++;

}

bool flag=StackEmpty(&st);

StackDestroy(&st);

return flag;

}

用队列实现栈--链接

动态演示

实现代码

// 链式结构：表示队列

typedef int QDataType;

typedef struct QListNode

{

struct QListNode* _next;

QDataType _data;

}QNode;

// 队列的结构

typedef struct Queue

{

QNode* _front;

QNode* _rear;

QDataType _size;

}Queue;

// 初始化队列

void QueueInit(Queue* q);

// 队尾入队列

void QueuePush(Queue* q, QDataType data);

// 队头出队列

void QueuePop(Queue* q);

// 获取队列头部元素

QDataType QueueFront(Queue* q);

// 获取队列队尾元素

QDataType QueueBack(Queue* q);

// 获取队列中有效元素个数

int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

bool QueueEmpty(Queue* q);

// 销毁队列

void QueueDestroy(Queue* q);

// 初始化队列

void QueueInit(Queue* q)

{

assert(q);

q->_front = q->_rear = NULL;

q->_size = 0;

}

// 队尾入队列

void QueuePush(Queue* q, QDataType data)

{

assert(q);

QNode* cur = (QNode*)malloc(sizeof(QNode));

if (cur == NULL)

{

perror("malloc fail");

exit(-1);

}

else

{

cur->_data = data;

cur->_next = NULL;

}

if (q->_rear == NULL)

{

q->_front = q->_rear = cur;

}

else

{

q->_rear->_next = cur;

q->_rear = cur;

}

q->_size++;

}

// 队头出队列

void QueuePop(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));

if (q->_front->_next==NULL)

{

free(q->_front);

q->_front = q->_rear = NULL;

}

else

{

QNode* cur = q->_front;

q->_front = q->_front->_next;

free(cur);

cur = NULL;

}

q->_size--;

}

// 获取队列头部元素

QDataType QueueFront(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));

return q->_front->_data;

}

// 获取队列队尾元素

QDataType QueueBack(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));

return q->_rear->_data;

}

// 获取队列中有效元素个数

int QueueSize(Queue* q)

{

assert(q);

return q->_size;

}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

bool QueueEmpty(Queue* q)

{

assert(q);

return q->_front == NULL && q->_rear == NULL;

}

// 销毁队列

void QueueDestroy(Queue* q)

{

assert(q);

QNode* cur = q->_front;

while (cur)

{

QNode* del = cur;

cur = cur->_next;

free(del);

del = NULL;

}

q->_front = q->_rear = NULL;

}

typedef struct {

Queue q1;

Queue q2;

} MyStack;

//创建队列形成的栈

MyStack* myStackCreate() {

MyStack* obj=(MyStack*)malloc(sizeof(MyStack));

QueueInit(&obj->q1);

QueueInit(&obj->q2);

return obj;

}

//压栈

void myStackPush(MyStack* obj, int x) {

if(!QueueEmpty(&obj->q1))

{

QueuePush(&obj->q1,x);

}

else

{

QueuePush(&obj->q2,x);

}

//出栈 QueuePop

int myStackPop(MyStack* obj) {

QNode* empty=&obj->q1;

QNode* nonempty=&obj->q2;

if(!QueueEmpty(&obj->q1))

{

empty=&obj->q2;

nonempty=&obj->q1;

}

while(QueueSize(nonempty)>1)

{

QueuePush(empty,QueueFront(nonempty));

QueuePop(nonempty);

}

int top=QueueFront(nonempty);

QueuePop(nonempty);

return top;

}

//栈顶值

int myStackTop(MyStack* obj) {

if(!QueueEmpty(&obj->q1))

{

return QueueBack(&obj->q1) ;

}

else

{

return QueueBack(&obj->q2);

}

//判断栈为空

bool myStackEmpty(MyStack* obj) {

return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);

}

//释放栈

void myStackFree(MyStack* obj) {

QueueDestroy(&obj->q1);

QueueDestroy(&obj->q2);

free(obj);

obj==NULL;

}

/**

* Your MyStack struct will be instantiated and called as such:

* MyStack* obj = myStackCreate();

* myStackPush(obj, x);

* int param_2 = myStackPop(obj);

* int param_3 = myStackTop(obj);

* bool param_4 = myStackEmpty(obj);

* myStackFree(obj);

用栈实现队列--链接

动态演示

实现代码

typedef int STDataType;

//#define N 10

//typedef struct Stack

//{

// STDataType _a[N];

// int _top; // 栈顶

//}Stack;

// 支持动态增长的栈

typedef int STDataType;

typedef struct Stack

{

STDataType* _a;

int _top; // 栈顶

int _capacity; // 容量

}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);

// 初始化栈

void StackInit(Stack* ps)

{

assert(ps);//断言传入地址是否为空

ps->_a = NULL;

ps->_capacity = ps->_top = 0;

}

// 入栈

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

if (ps->_top == ps->_capacity)

{

int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity*2;//判断容量是否为空并设置增加容量数量

STDataType* temp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));//增加容量

if (temp == NULL)//判断地址是否开辟成功

{

perror("realloc fail");

exit(-1);

}

ps->_a = temp;//赋址与结构体中

ps->_capacity = newCapacity;//更新容量

}

ps->_a[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->_a[ps->_top-1];

}

// 获取栈中有效元素个数

int StackSize(Stack* ps)

{

assert(ps);

return ps->_top;

}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0

bool StackEmpty(Stack* ps)

{

assert(ps);

return ps->_top==0;

}

// 销毁栈

void StackDestroy(Stack* ps)

{

assert(ps);

free(ps->_a);//清除数组地址

ps->_a = NULL;

ps->_top = ps->_capacity = 0;

}

typedef struct {

Stack push;

Stack pop;

} MyQueue;

MyQueue* myQueueCreate() {

MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));

StackInit(&obj->push);

StackInit(&obj->pop);

return obj;

}

void myQueuePush(MyQueue* obj, int x) {

StackPush(&obj->push,x);

}

int myQueuePop(MyQueue* obj) {

if(StackEmpty(&obj->pop))

{

while(!StackEmpty(&obj->push))

{

StackPush(&obj->pop,StackTop(&obj->push));

StackPop(&obj->push);

}

STDataType tem =StackTop(&obj->pop);

StackPop(&obj->pop);

return tem;

}

int myQueuePeek(MyQueue* obj) {

if(StackEmpty(&obj->pop))

{

while(!StackEmpty(&obj->push))

{

StackPush(&obj->pop,StackTop(&obj->push));

StackPop(&obj->push);

}

return StackTop(&obj->pop);

}

bool myQueueEmpty(MyQueue* obj) {

return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);

}

void myQueueFree(MyQueue* obj) {

StackDestroy(&obj->push);

StackDestroy(&obj->pop);

free(obj);

}

/**

* Your MyQueue struct will be instantiated and called as such:

* MyQueue* obj = myQueueCreate();

* myQueuePush(obj, x);

* int param_2 = myQueuePop(obj);

* int param_3 = myQueuePeek(obj);

* bool param_4 = myQueueEmpty(obj);

* myQueueFree(obj);

设计循环队列--链接

用数组更好还是链表

在考虑用谁更好时，有个问题已经来了，如何判断满和空

判断空只需要front==rear就为空

判断满有两个方法： 1.用size计数 2.增加一个空节点

这里如果用size的话我们发现实现循环还是需要加节点，那如果不加呢？

不加节点我们发现，先走的rear，如果满了rear与front就重复了到底是空还是满就不好判断。所以这里我们选择加节点。

当加了节点我们发现循环之后需要获取队列最后一个元素时，需要重新遍历或者加一个指向前面的指针

当我们决定用数组时我们需要注意什么呢？

当rear进行循环时，rear+1会出现越界的问题，如何解决呢？

我们只需要（rear+1）%rear 即可，就可以进行循环。

动态演示

实现代码

typedef struct {

int *a;

int front;

int rear;

int N;

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {

MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));

obj->a=(int*)malloc((k+1)*sizeof(int));

obj->front=obj->rear=0;

obj->N=k+1;

return obj;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

return obj->front==obj->rear;

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

return (obj->rear+1)%obj->N==obj->front;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

if( myCircularQueueIsFull(obj))

return false;

obj->a[obj->rear]=value;

obj->rear++;

obj->rear %= obj->N;

return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

if(myCircularQueueIsEmpty(obj))

return false;

obj->front++;

obj->front %= obj->N;

return true;

}

int myCircularQueueFront(MyCircularQueue* obj) {

if(myCircularQueueIsEmpty(obj))

return -1;

else

return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj) {

if(myCircularQueueIsEmpty(obj))

return -1;

else

return obj->a[(obj->rear+obj->N-1)%obj->N];

}

void myCircularQueueFree(MyCircularQueue* obj) {

free(obj->a);

free(obj);

}

/**

* Your MyCircularQueue struct will be instantiated and called as such:

* MyCircularQueue* obj = myCircularQueueCreate(k);

* bool param_1 = myCircularQueueEnQueue(obj, value);

* bool param_2 = myCircularQueueDeQueue(obj);

* int param_3 = myCircularQueueFront(obj);

* int param_4 = myCircularQueueRear(obj);

* bool param_5 = myCircularQueueIsEmpty(obj);

* bool param_6 = myCircularQueueIsFull(obj);

* myCircularQueueFree(obj);

查看原文

夸智网

c语言算法链表数据结构--栈，队列

c语言【数据结构与算法】时间复杂度和空间复杂度

java spring boot 后端 MyBatis-plus实现逆向生成器

发表评论取消回复

夸智网

c语言 算法 链表 数据结构--栈，队列

c语言 【数据结构与算法】时间复杂度和空间复杂度

java spring boot 后端 MyBatis-plus实现逆向生成器

相关文章

发表评论取消回复

c语言算法链表数据结构--栈，队列

c语言【数据结构与算法】时间复杂度和空间复杂度