当前位置： 首页 > article >正文

【数据结构】栈与队列

article 2025/2/5 17:55:07

栈

栈的概念及结构

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

在这里插入图片描述

栈的实现

一般可以使用数组或链表，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小在这里插入图片描述

在这里插入图片描述
用数组实现：

Stack.h

#pragma once

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

//#define N 10
//struct Stack {
//	int a[N];
//	int top;
//};

typedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);

void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);

STDataType STTop(ST* ps);

Stack.c

#include "Stack.h"

void STInit(ST* ps) {
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL) {
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	//ps->top = -1;//top栈顶元素位置
	ps->top = 0;//top栈顶元素下一个位置
}
void STDestroy(ST* ps) {
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps, STDataType x) {
	assert(ps);

	if (ps->top == ps->capacity) {
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (ps->a == NULL) {
			perror("malloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}
int STSize(ST* ps) {
	assert(ps);

	return ps->top;
}
bool STEmpty(ST* ps) {
	assert(ps);

	return ps->top == 0;
}

STDataType STTop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

Test.c

#pragma once

#include "Stack.h"

int main() {
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	//while (!STEmpty(&st)) {
	while (st.top!=0) {
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
	return 0;
}

例1：

在这里插入图片描述
方法：
左括号入栈
右括号于出栈顶的那个左括号匹配
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

队列

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
在这里插入图片描述
Queue.h

#pragma once

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.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);//头删
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDataType QueueFront(Queue* pq);//队头的数据
QDataType QueueBack(Queue* pq);//队尾的数据

Queue.c

#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* next = cur->next;
		free(cur);
		cur = next;
	}
}

void QueuePush(Queue* pq, QDataType x) {
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode -> data = x;
	newnode->next = NULL;

	if (newnode == NULL) {
		perror("malloc fail");
		return;
	}
	if (pq->head == NULL) {
		assert(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(pq->head != NULL);

	/*QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	if (pq->head == NULL) {
		pq->tail = NULL;
	}*/

	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}


	pq->size--;
}

int QueueSize(Queue* pq) {
	assert(pq);

	return pq->size;
}

bool QueueEmpty(Queue* pq) {
	assert(pq);

	return pq->size == 0;
}

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

Test.c

#pragma once

#include "Queue.h"

int main() {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q)) {
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
	return 0;
}

例2：

在这里插入图片描述
方法：
保持一个队列为空，一个队列存数据
出栈，把前面数据导入空队列

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);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

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* next = cur->next;
		free(cur);
		cur = next;
	}
}

void QueuePush(Queue* pq, QDataType x) {
	QNode* newnode = (QNode*)malloc(sizeof(QNode));

	if (newnode == NULL) {
		perror("malloc fail");
		return;
	}
    newnode -> data = x;
	newnode->next = NULL;

	if (pq->head == NULL) {
		assert(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(pq->head != NULL);

	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

int QueueSize(Queue* pq) {
	assert(pq);

	return pq->size;
}

bool QueueEmpty(Queue* pq) {
	assert(pq);

	return pq->size == 0;
}

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

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    if(pst==NULL){
        perror("malloc fail");
        return NULL;
    }
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);  
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1)){
        QueuePush(&obj->q1,x);
    }else
        QueuePush(&obj->q2,x);
}

int myStackPop(MyStack* obj) {
    Queue* emptyQ=&obj->q1;
    Queue* nonemptyQ=&obj->q2;
    if(!QueueEmpty(emptyQ)){
        emptyQ=&obj->q2;
        nonemptyQ=&obj->q1;
    }

    while(QueueSize(nonemptyQ)>1){
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }

    int top=QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    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);
}

/**
 * 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);
*/

例3

在这里插入图片描述

分为两个栈，一个进数据pushst，一个出数据popst
当需要出数据时，分为两种情况，
1，popst中没有数据时，需要将pushst的数据导入popst中，此时popst中数据顺序与pushst中相反
正常出数据即可
2.popst中有数据时，正常出数据即可

#pragma once

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

typedef int STDataType;

typedef struct Stack {
	int* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);

void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);

STDataType STTop(ST* ps);

void STInit(ST* ps) {
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL) {
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;
}
void STDestroy(ST* ps) {
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps, STDataType x) {
	assert(ps);

	if (ps->top == ps->capacity) {
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (ps->a == NULL) {
			perror("malloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}
int STSize(ST* ps) {
	assert(ps);

	return ps->top;
}
bool STEmpty(ST* ps) {
	assert(ps);

	return ps->top == 0;
}

STDataType STTop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL){
        perror("malloc fail");
        return NULL;
    }
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->pushst,x);
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst)){
        while(!STEmpty(&obj->pushst)){
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }

    return STTop(&obj->popst);
}

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    STPop(&obj->popst);

    return front;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    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);
*/

例4：

在这里插入图片描述

typedef struct {
    int* a;
    int front;
    int rear;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front=obj->rear=0;
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    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->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;
    else
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else{
        int x=obj->rear==0?obj->k:obj->rear-1;
        return obj->a[x];
    }
        
    //return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}

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);
*/

http://www.kler.cn/a/532732.html

相关文章：

  • Spring Bean 的生命周期介绍
  • 生成式AI安全最佳实践 - 抵御OWASP Top 10攻击 (下)
  • RK3566-移植5.10内核Ubuntu22.04
  • 蓝桥杯备考：高精度算法之除法
  • html中的表格属性以及合并操作
  • 进阶数据结构——双向循环链表
  • redis简介及应用
  • RK3566-移植5.10内核Ubuntu22.04
  • 数据结构：优先级队列— PriorityQueue
  • 04树 + 堆 + 优先队列 + 图（D1_树（D17_综合刷题练习））
  • Shell 中的 Globbing：原理、使用方法与实现解析（中英双语）
  • DeepSeek相关技术整理
  • 基于RTOS的STM32游戏机
  • 电商项目高级篇09-检索服务
  • Linux find 命令 | grep 命令 | 查找 / 列出文件或目录路径 | 示例
  • 2025美赛赛前准备笔记（论文手）
  • 【IoCDI】_@Bean的参数传递
  • leetcode 901. 股票价格跨度
  • 【玩转 Postman 接口测试与开发2_016】第13章：在 Postman 中实现契约测试（Contract Testing）与 API 接口验证（上）
  • 【25考研】南开软件考研复试复习重点！
  • redis实现延迟任务
  • 结构体排序 C++ 蓝桥杯
  • C++引用练习题
  • 基于springboot的电影评论网站(源码+数据库+文档)
  • PVE纵览-实现极致性能：在Proxmox VE中配置硬盘直通
  • Office / WPS 公式、Mathtype 公式输入花体字、空心字