行业知识
数据结构---栈和队列
2026-11-14 20:50:43
来源：互联网转载
���录
1、栈
1.1 栈的概念及结构
1.2 栈的实现
1.2.3 栈的实现代码
2.队列
2.1 队列的概念和结构
2.2 队列的实现
2.3 队列代码实现
2.3 循环队列
3.扩展
3.1 使用队列实现栈oj链接
3.2 使用栈实现队列oj链接
1、栈
1.1 栈的概念及结构
栈：栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除的一端称之为栈顶，另一端称为栈底。栈中的元素遵循先进后出原则
压栈：栈的插入操作叫做进栈/压栈/入栈。栈顶入数据。
出栈：栈的删除操作叫做出栈，栈底出数据。
1.2 栈的实现
栈一般有数组栈和链式栈两种，可以使用数组或者链表来实现，相对而言数组的结构实现比链表实现更优一些，因为数组的尾插的代价较小。
1.2.3 栈的实现代码
Stack.h
//Stack.h#pragma once#include#include#include// 支持动态增长的栈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 int 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 = 0;ps->_top = 0;}// 入栈 void StackPush(Stack* ps, STDataType data) {assert(ps);if (ps->_capacity == ps->_top) {int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc fail");return;}ps->_a = tmp;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);return ps->_a[ps->_top - 1];}// 获取栈中有效元素个数 int StackSize(Stack* ps) {assert(ps);return ps->_top;}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps) {assert(ps);if (ps->_top == 0) {return 1;}else {return 0;}}// 销毁栈 void StackDestroy(Stack* ps) {assert(ps);free(ps->_a);ps->_a = NULL;ps->_capacity = ps->_top = 0;} 2.队列
2.1 队列的概念和结构
队列:只允许一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出原则，进行插入操作的一端成为队尾，进行删除操作的一端称为队头,队尾插入数据，队头出数据。
2.2 队列的实现
队列和栈一样都有数组和链表两种实现结构，但是和数组不同的是队列一般使用链表实现，因为出队列是在队头，相对数组而言，链表效率更高。
2.3 队列代码实现
Queue.h
#pragma once#include#include#include// 链式结构：表示队列typedef int QDataType;typedef struct QListNode{struct QListNode* _next;QDataType _data;}QNode;// 队列的结构 typedef struct Queue{QNode* _front;QNode* _rear;int 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 int QueueEmpty(Queue* q);// 销毁队列 void QueueDestroy(Queue* q); Queue.c
#define _CRT_SECURE_NO_WARNINGS#include"Queue.h"// 初始化队列 void QueueInit(Queue* q) {q->_front = q->_rear = NULL;q->size = 0;}// 队尾入队列 void QueuePush(Queue* q, QDataType data) {assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail");return NULL;}newnode->_data = data;newnode->_next = NULL;if (q->_front == NULL) {q->_front = q->_rear = newnode;q->size++;}else {q->_rear->_next = newnode;q->_rear = newnode;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* del = q->_front;q->_front = q->_front->_next;free(del);del = 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 int QueueEmpty(Queue* q) {assert(q);if (q->size == 0) {return 1;}else {return 0;}}// 销毁队列 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;q->size = 0;} 2.3 环形队列
oj链接. - 力扣（LeetCode）
typedef struct { int front; int rear; int k; int*a;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->rear=0; obj->k=k; return obj;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->rear;}bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1)==obj->front;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)){ return false; } obj->a[obj->rear]=value; obj->rear++; obj->rear%=obj->k+1; return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)){ return false; } obj->front++; obj->front%=(obj->k+1); 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; } return obj->a[(obj->rear+obj->k)%(obj->k+1)];}void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj);} 3.扩展
3.1 使用队列实现栈oj链接
// 链式结构：表示队列typedef int QDataType;typedef struct QListNode{struct QListNode* _next;QDataType _data;}QNode;// 队列的结构 typedef struct Queue{QNode* _front;QNode* _rear;int 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 int QueueEmpty(Queue* q);// 销毁队列 void QueueDestroy(Queue* q);// 初始化队列 void QueueInit(Queue* q) {q->_front = q->_rear = NULL;q->size = 0;}// 队尾入队列 void QueuePush(Queue* q, QDataType data) {assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail");}newnode->_data = data;newnode->_next = NULL;if (q->_front == NULL) {q->_front = q->_rear = newnode;q->size++;}else {q->_rear->_next = newnode;q->_rear = newnode;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* del = q->_front;q->_front = q->_front->_next;free(del);del = 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 int QueueEmpty(Queue* q) {assert(q);if (q->size == 0) {return 1;}else {return 0;}}// 销毁队列 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;q->size = 0;}typedef struct { Queue q1; Queue q2;} MyStack;MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); if(obj==NULL){ perror("molloc fail"); return NULL; } 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); }}int myStackPop(MyStack* obj) { Queue* pEmpty =&obj->q1; Queue* pNotEmpty =&obj->q2; if(!QueueEmpty(&obj->q1)){ pEmpty = &obj->q2; pNotEmpty =&obj->q1; } while(QueueSize(pNotEmpty)>1){ QueuePush(pEmpty,QueueFront(pNotEmpty)); QueuePop(pNotEmpty); } int top=QueueFront(pNotEmpty); QueuePop(pNotEmpty); 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);} 3.2 使用栈实现队列oj链接
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);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0int StackEmpty(Stack* ps);// 销毁栈void StackDestroy(Stack* ps);void StackInit(Stack* ps) { assert(ps); ps->_a = NULL; ps->_capacity = 0; ps->_top = 0;}// 入栈void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->_capacity == ps->_top) { int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } ps->_a = tmp; 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); return ps->_a[ps->_top - 1];}// 获取栈中有效元素个数int StackSize(Stack* ps) { assert(ps); return ps->_top;}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0int StackEmpty(Stack* ps) { assert(ps); if (ps->_top == 0) { return 1; } else { return 0; }}// 销毁栈void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a = NULL; ps->_capacity = ps->_top = 0;}typedef struct { Stack pushst; Stack popst;} MyQueue;MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL){ perror("malloc fail"); } StackInit(&obj->popst); StackInit(&obj->pushst); return obj;}void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushst,x);}int myQueuePop(MyQueue* obj) { int front=myQueuePeek(obj); StackPop(&obj->popst); return front;}int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popst)){ while(!StackEmpty(&obj->pushst)){ StackPush(&obj->popst,StackTop(&obj->pushst)); StackPop(&obj->pushst); } } return StackTop(&obj->popst);}bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst);}void myQueueFree(MyQueue* obj) { StackDestroy(&obj->pushst); StackDestroy(&obj->popst); free(obj);}
