栈和队列的区别和应用场景

创作时间:

作者:

@小白创作中心

栈和队列的区别和应用场景

引用

CSDN

https://blog.csdn.net/weixin_33398032/article/details/141424700

栈和队列是计算机科学中两种基本且重要的数据结构，它们分别遵循“先进后出”和“先进先出”的原则，在程序设计和算法实现中有着广泛的应用。本文将详细介绍栈和队列的区别、实现方式以及具体应用场景。

1 栈和队列区别

栈：先进后出
队列：先进先出

2 栈和队列的实现

栈的实现

栈可以通过数组或链表来实现。如果采用数组实现，可以将数组尾部作为栈顶，并保存数组尾部元素下标进行压栈和出栈操作；如果采用链表实现，则可以采用头插法，并保存头指针进行压栈和出栈操作。

typedef int STDataType;
typedef struct Stack
{
    STDataType* array;
    int capacity;
    int top;   // 栈顶位置的下一个位置的下标
}Stack;
 
//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶数据
STDataType StackTop(Stack* ps);
//栈的大小
int StackSize(Stack* ps);
//栈是否为空
bool StackEmpty(Stack* ps);

队列的实现

队列通常采用链表来实现。采用尾插法，并保存尾指针，入队时插入链表尾部，出队时从链表头进行出队操作。

//数据类型
typedef int QDataType;
//队列结点
typedef struct QueueNode
{
    QDataType val;
    struct QueueNode* next;
}QueueNode;
//队列结构体
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
    int size;
}Queue;
 
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//队列是否为空
bool QueueEmpty(Queue* pq);
//队列的大小
int QueueSize(Queue* pq);

3 栈和队列的应用场景

栈和队列是两种重要的数据结构，它们在计算机科学和软件工程中有着广泛的应用。栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。它们各自具有独特的特性和应用场景，下面将详细介绍这些应用场景。

3.1 栈的应用场景

撤销操作：在许多软件应用程序中，每当用户执行一个操作（如添加、删除或修改），相关信息会被推入栈中。当用户选择撤销时，程序将从栈中弹出最近的操作并还原到上一个状态。
后退/前进功能：网页浏览器中的后退和前进按钮使用栈来实现。每次访问一个新页面时，页面信息被推入栈中。点击后退按钮时，程序从栈中弹出最近的访问页面，显示上一个页面。
递归算法：递归算法也使用栈来实现。每次递归调用时，函数的当前状态（包括参数和局部变量）被推入栈中。当递归函数结束时，栈会弹出并还原上一个状态。
表达式求值：在算术表达式的求值中，栈用于处理运算符的优先级和处理括号匹配等问题。
括号匹配：在编译器的语法分析阶段，栈用于检查源代码中的括号是否正确匹配。