目录
- 前言
- 栈
- 队列
- 实例分析
- 结语
前言
本篇文章主要讲述数据结构中栈和队列的实现,以及相关实例分析。
栈
注意本文所讲述的栈是数据结构的一种,并不是内存划区中的栈区,但是这两者有相似之处,即:存储数据时满足数据先进后出的特点,除此之外还有以下特点:
(1)访问栈时,只能访问栈顶数据,要想访问栈底数据,需将栈顶数据一步步移除;
(2)栈不支持随机访问和随机插入;
通过图形表达如下:
数据只能从一端进入,从一端走出,要想获得栈底的数据就必须将上面的数据移除,同时是无法获取栈中间的数据的。
鉴于栈的特点,我觉得通过顺序表实现是最方便的,以下是实现代码:
//stack.h
#pragma once
#include<assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 支持动态增长的栈
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->top = 0;ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 2 : ps->capacity * 2;STDataType* pa = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (pa == NULL){perror("malloc fail");exit(-1);}ps->a = pa;ps->capacity = newcapacity;}ps->a[ps->top] = data;ps->top++;
}
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
//test.c
#define _CRT_SECURE_NO_WARNINGS
#include "stack.h"
void test1()
{Stack ps;StackInit(&ps);StackPush(&ps, 1);StackPush(&ps, 2);printf("%d\n", StackSize(&ps));printf("%d ", StackTop(&ps));StackPop(&ps);StackPush(&ps, 3);printf("%d ", StackTop(&ps));StackPop(&ps);StackPush(&ps, 4);while (!StackEmpty(&ps)){printf("%d ", StackTop(&ps));StackPop(&ps);}printf("\n%d", StackSize(&ps));StackDestroy(&ps);
}
int main()
{test1();return 0;
}
队列
队列存储数据的方式和栈刚好相反,满足先进先出的原则,通过图形表达如下:
队列数据从一端进入,从另一端走出,先进入队列的数据先出,同样的无法访问队列中间的数据,但是队列可以访问队首和队尾的数据。
了解完特点,鉴于需要头部删除,尾部插入,个人觉得链表更适合模拟实现,接下来模拟实现,代码如下:
//queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//数据类型
typedef int QDataType;
//队列的每个节点
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* front;QNode* back;
}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
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
void QueueInit(Queue* q)
{assert(q);q->back = q->front = NULL;
}
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* pa = (QNode*)malloc(sizeof(QNode));if (pa == NULL){perror("malloc fail");exit(-1);}pa->data = data;pa->next = NULL;if (q->front == NULL){q->back = q->front = pa;}else{q->back->next = pa;q->back = pa;}
}
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QNode* del = q->front;q->front = q->front->next;free(del);del = NULL;
}
bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->back->data;
}
int QueueSize(Queue* q)
{assert(q);int count = 0;QNode* cur = q->front;while (cur){count++;cur = cur->next;}return count;
}
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* del = cur;cur = cur->next;free(del);}cur = NULL;q->back = q->front = NULL;
}
//test.c
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
void test()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);//printf("%d ", QueueFront(&q));//QueuePop(&q);QueuePush(&q, 4);QueuePush(&q, 5);printf("\n%d\n", QueueSize(&q));while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}//QueuePop(&q);QueueDestroy(&q);
}
int main()
{test();return 0;
}
以上就是栈和队列的实现,实现方法只是个人觉得更合适,当然还有其他的实现方法,比如通过链表实现栈(插入删除数据就用头插头删),顺序表实现队列(这里就需要不停的挪动数据了)等,接下来通过实例来感受栈和队列的特点和如何互相实现对方的。
实例分析
- 用队列实现栈
这道题设计栈的方法是通过两个队列来实现的,那么如何实现呢?
通过上文我们知道了栈的性质,现在假如有两个队列,如下所示:
假设数据先存储在队列1中,当我们需要弹出数据时,按照栈后进先出的特性,我们需要先将队列1尾部数据之前的所有数据存储在队列2中,然后弹出队列1的数据,如图:
那我们还需要弹出数据该怎么做呢,一样的,先将队列2尾部数据之前的所有数据先挪动到队列1中,然后弹出队列2的数据,就像这样:
如此反复,直至两个队列都为空队列说明数据已全部弹出,接下来就是代码实现:
typedef int QDataType;typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* front;QNode* back;
}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->back = q->front = NULL;
}
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* pa = (QNode*)malloc(sizeof(QNode));if (pa == NULL){perror("malloc fail");exit(-1);}pa->data = data;pa->next = NULL;if (q->front == NULL){q->back = q->front = pa;}else{q->back->next = pa;q->back = pa;}
}
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QNode* del = q->front;q->front = q->front->next;free(del);del = NULL;
}
bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->back->data;
}
int QueueSize(Queue* q)
{assert(q);int count = 0;QNode* cur = q->front;while (cur){count++;cur = cur->next;}return count;
}
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* del = cur;cur = cur->next;free(del);}cur = NULL;q->back = q->front = 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) {assert(obj);//数据往非空的队列插入if(QueueEmpty(&obj->Q1)){QueuePush(&obj->Q2, x);}else{QueuePush(&obj->Q1, x);}
}bool myStackEmpty(MyStack* obj) {assert(obj);//栈为空,则两个队列均为空return QueueEmpty(&obj->Q1) && QueueEmpty(&obj->Q2);
}int myStackPop(MyStack* obj) {assert(obj);//栈为空不可以删除assert(!myStackEmpty(obj));//将非空队列尾数据之前的所有数据挪动到空队列,然后弹出这个尾数据Queue* empty = &obj->Q1;Queue* noempty = &obj->Q2;if(QueueEmpty(&obj->Q2)){empty = &obj->Q2;noempty = &obj->Q1;}while(QueueSize(noempty)>1){QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}QDataType ret = QueueFront(noempty);QueuePop(noempty);return ret;
}int myStackTop(MyStack* obj) {assert(obj);//栈为空则没有数据assert(!myStackEmpty(obj));Queue* empty = &obj->Q1;Queue* noempty = &obj->Q2;if(QueueEmpty(&obj->Q2)){empty = &obj->Q2;noempty = &obj->Q1;}//返回的是非空队列的尾数据return QueueBack(noempty);
}void myStackFree(MyStack* obj) {
//释放不仅要释放结构体栈,还要释放其包含的两个队列QueueDestroy(&obj->Q1);QueueDestroy(&obj->Q2);free(obj);
}
由于C语言没有提供队列的实现,所以我们调用队列时需要自己实现,关于怎么实现我已在上面介绍过,这里我就直接用了。
2.用栈实现队列
同样的这里需要用两个栈来实现队列,栈的特性是后进先出,那么如何模拟出先进先出呢?我们通过图来表达:
这里我们将两个栈分别规定一下,假设一个栈专门用于存储数据为A,另一个专门用于弹出数据为B,当我们需要弹出数据时,先判断B队列是否为空,不为空就可以出栈,为空就需要栈A将所有的数据全部导入栈B中,入后出栈,如此就可以实现队列的先进先出了,如下图所示:
值得注意的是,这里当栈B不为空时,是不可以将栈A中的数据挪动到栈B中的,接下来就是代码实现(由于C语言不带栈的实现,所以需要自己实现):
// 支持动态增长的栈
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->top = 0;ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 2 : ps->capacity * 2;STDataType* pa = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (pa == NULL){perror("malloc fail");exit(-1);}ps->a = pa;ps->capacity = newcapacity;}ps->a[ps->top] = data;ps->top++;
}
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
//上述是实现栈
//结构体队列(包含两个栈)
typedef struct {Stack in;Stack out;
} MyQueue;MyQueue* myQueueCreate() {//为队列开辟空间MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));assert(obj);//为队列包含的两个栈开辟空间StackInit(&obj->in);StackInit(&obj->out);return obj;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);//往栈A存储数据StackPush(&obj->in, x);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->in) && StackEmpty(&obj->out);
}int myQueuePop(MyQueue* obj) {assert(obj);//队列为空不可以删除assert(!myQueueEmpty(obj));//出队列的数据就是栈B栈顶的数据if(StackEmpty(&obj->out)){while(!StackEmpty(&obj->in)){StackPush(&obj->out, StackTop(&obj->in));StackPop(&obj->in);}}int ret = StackTop(&obj->out);StackPop(&obj->out);return ret;
}
//队列队尾的数据就是栈A栈顶的数据
int myQueuePeek(MyQueue* obj) {assert(obj);assert(!myQueueEmpty(obj));if(StackEmpty(&obj->out)){while(!StackEmpty(&obj->in)){StackPush(&obj->out, StackTop(&obj->in));StackPop(&obj->in);}}return StackTop(&obj->out);
}void myQueueFree(MyQueue* obj) {
//释放空间要完全StackDestroy(&obj->in);StackDestroy(&obj->out);free(obj);
}
3.设计循环队列
要实现循环队列,我们需要先知道什么是循环队列。循环队列就是在逻辑上是闭环的,形如下图:
由于在内存地址上是不可能循环的,所以我们需要通过设计来实现循环,解决这回个问题有两个思路:(1)循环链表,利用我们之前是先过的双向循环链表实现(2)用顺序表实现;这两个方法都可以,那么我在这里通过顺序表来实现循环队列。实现过程中,我们需要注意的是什么时候队列满了,什么时候队列为空,首先我们需要两个指针分别指向首尾,如下图所示:
我们向内存申请k+1个空间,然后把数据插入到back指针所指向的位置,然后back++,当back++等于head时说明循环队列已满,当back等于head时说明队列为空,有了思路代码实现就容易了起来:
//匿名结构体,将队列首地址,首尾下表,顺序表长度k+1封装
typedef struct {int* Queue;int head;int back;int size;
} MyCircularQueue;
//创造循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
//创建队列MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//为顺序表申请空间,空间大小为k+1obj->Queue = (int*)malloc((k+1)*sizeof(int));obj->head = obj->back = 0;obj->size = k+1;return obj;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);//首尾指针相等就为空,这里取模原因在于避免back超出顺序表的范围,预防越界访问return (obj->back+1) % obj->size == obj->head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if(myCircularQueueIsFull(obj)){return 0;}obj->Queue[obj->back] = value;obj->back++;//避免back超出顺序表的范围obj->back %= obj->size;return 1;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);//循环队列为空即首尾指针相等return obj->head == obj->back;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return 0;}obj->head++;//避免head超出顺序表的范围obj->head %= obj->size;return 1;
}int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->Queue[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}//队尾的数据一般情况是back-1位置的数据,但在back==0时,需要特殊处理,让back-1等于k,此时(back-1+size)%size刚好满足使用return obj->Queue[(obj->back-1+obj->size)%obj->size];
}void myCircularQueueFree(MyCircularQueue* obj) {
//要完全释放空间free(obj->Queue);free(obj);
}
结语
以上就是本篇文章的全部内容了,通过三个实例充分的展示了栈和队列的实现方法是很多种的,同时关于巧用取模操作也是值得我们学习的。