栈和队列简单应用
通篇使用C语言实现
本文会直接使用写好的栈和队列，而且与上文为姐妹篇，好多内容是基于上文展开的。
前言
通过几道例题可以帮助熟悉栈和队列的性质与使用
栈是将数据由栈顶放入，但也只能由栈顶出数据只能通过栈顶操作。
队列由队头和队尾一起操作，是由对尾入数据，队头出数据。
用栈实现队列
栈只能由栈顶出入数据，为了实现由队尾入数据队头出数据的队列，可以借助两个栈来回导数据，一个用来插入，一个用来删除。
数据入队列即将数据放入插入栈。
数据出队列即将插入栈的数据逐一放入删除栈，直到遇到需要删除的数据在插入栈删除即可。
push主要插入时使用，pop删除时使用
比如将队头的一删除后，2就变成了队头，再去看图中不同栈的功能。
说白了也是构造自己的函数，因为是C语言实现，没有STL库，需要借助栈和队列的一些内容。
使用C语言简单实现
- 先把栈拿过来
//栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //栈顶的位置
int capacity; //容量
}ST;
//队列结构
typedef struct {
ST* push;
ST* pop;
} MyQueue;
void StackInit(ST* ps)//栈的初始化
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestory(ST* ps)//栈的销毁
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)//插入数据
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)//删除数据
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
bool StackEmpty(ST* ps)//判断栈是否为空
{
assert(ps);
return ps->top == 0;
}
int StackSize(ST* ps)//栈内元素数量
{
assert(ps);
return ps->top;
}
STDataType StackTop(ST* ps)//获得栈顶元素
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
队列结构
//队列结构
typedef struct {
ST* push;
ST* pop;
} MyQueue;
队列实现
队列创建
MyQueue* myQueueCreate()
MyQueue* myQueueCreate() { MyQueue* newqueue = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&newqueue->push); StackInit(&newqueue->pop); return newqueue; }正常操作
插入数据
void myQueuePush(MyQueue* obj, int x)
void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->push, x); }判空等安全操作已在栈中实现
删除数据
int myQueuePop(MyQueue* obj)
int myQueuePop(MyQueue* obj) { assert(obj); if (StackEmpty(&obj->pop) == NULL)//某个栈内没有元素 { while (StackEmpty(&obj->push) != NULL)//另一个栈中有元素，直到队头数据出现 { StackPush(&obj->pop, StackTop(&obj->push));把有元素的栈的栈顶数据放入另一个栈 StackPop(&obj->push);//删除一下原栈中已经转移的数据 } } int before = StackTop(&obj->pop);//记录了原栈最后一个数据 StackPop(&obj->pop);//删除了（对头数据）//这里将需要删除的数据也转移了一下 return before;//返回了删除的元素 }
图解是通用的，而且每行代码都有解释
返回队列开头的数据
int myQueuePeek(MyQueue* obj)
int myQueuePeek(MyQueue* obj) { assert(obj); if (StackEmpty(&obj->pop) == NULL)//数据转到的栈没有数据 { return StackTop(&obj->push);//原栈不过有没有返回即可 } return StackTop(&obj->pop);//pop栈中有数据，栈顶就是队头 }理清两个栈的作用
判断队列是否为空
bool myQueueEmpty(MyQueue* obj)
bool myQueueEmpty(MyQueue* obj) { assert(obj); if (obj->push == NULL && obj->pop == NULL)//两个栈都为空 { return true; } else { return false; } }
队列销毁
void myQueueFree(MyQueue* obj)
void myQueueFree(MyQueue* obj) { assert(obj); StackDestory(&obj->push); StackDestory(&obj->pop); free(obj); }要从内到外
用队列实现栈
队列有着对尾入数据队头出数据的特点
栈只能顶进顶出
那么可以用两个队列，数据入栈时将数据输入q1队列，出栈时由q1队列队头出数据导入q2队列，知道遇到栈顶（也就是q1队列最后一个数据）删除即可。
这里q1，q2两个队列需要多次互相导数据，q1，q2的功能也会互相转换。
使用C语言简单实现
首先把队列拿过来
#pragma once
// 链式结构：表示队列
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
}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
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
#include "Queue.h"
// 链式结构：表示队列
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = data;
newnode->next = NULL;
if (q->rear == NULL)
{
assert(q->front == NULL);
q->front = q->rear = newnode;
}
else
{
q->rear->next = newnode;
q->rear = newnode;
}
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->front && q->rear);
if (q->front->next == NULL)
{
q->front = q->rear == NULL;
}
else
{
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
if (q->front == NULL && q->rear == NULL)
{
return NULL;
}
return q->front->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
if (q->front == NULL && q->rear == NULL)
{
return NULL;
}
return q->rear->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
QNode* cur = q->front;
int size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
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;
}
将元素 x 压入栈顶
void myStackPush(MyStack* obj, int x)
void myStackPush(MyStack* obj, int x) { assert(obj); if(!QueueEmpty(&obj->q1))//不为空 { QueuePush(&obj->q1,x); } else//空不空为所谓 { QueuePush(&obj->q2,x); } }压栈时优先将数据放入不为空的队列中，都为空时随意放入即可。
移除并返回栈顶元素
int myStackPop(MyStack* obj)
int myStackPop(MyStack* obj) { assert(obj); Queue* emptQ = &obj->q1;//有数据（假设） Queue* nonEmptyQ = &obj->q2;//没有数据 if(!QueueEmpty(&obj->push))//判断 { emptQ = &obj->q2; nonEmptyQ = &obj->q1; } while(QueueSize(nonEmptyQ)>1) { int front = QueueFront(nonEmptyQ); QueuePush(emptQ, front);//将头放入空队列 QueuePop(nonEmptyQ);//转移后删除即可 } int top = QueueFront(nonEmptyQ);//记录并删除 QueuePop(nonEmptyQ); return top; }
返回栈顶元素
int myStackTop(MyStack* obj)
int myStackTop(MyStack* obj) { assert(obj); if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } }判一下空就好
如果栈是空的，返回 true ；否则，返回 false
bool myStackEmpty(MyStack* obj)
bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); }q1,q2都是空栈才是空
free
void myStackFree(MyStack* obj)
void myStackFree(MyStack* obj) { assert(obj); QueueDestroy(&obj->push); QueueDestroy(&obj->pop); free(obj); }从内到外
循环队列
- 思路见图
代码如下
其实没有必要逐行注释，不管是哪方面来看博主所写的代码思想都是易懂的
typedef struct {
int* a;
int front;
int tail;
int k;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int)*(k+1));
obj->front = obj->tail = 0;
obj->k = k;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->tail] = value;
if(obj->tail == obj->k)
{
obj->tail = 0;
}
else
{
obj->tail++;
}
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
if(obj->front == obj->k)
{
obj->front = 0;
}
else
{
obj->tail++;
}
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
if(obj->tail == 0)
{
return obj->a[obj->k];
}
else
{
return obj->a[obj->tail-1];
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
if(obj->tail == obj->k && obj->front == 0)
{
return true;
}
else
{
return obj->tail+1 == obj->front;
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}
总结
栈和队列的简单应用，是博主起记忆笔记作用的整理，三块内容也是力扣的原题
下次上二叉树
