数据结构-限定性线性表 - 栈与队列

     栈和队列是数据结构中非常重要的两种限定性线性表，它们在实际应用中有着广泛的用途。这篇文章将深入讲解栈和队列的概念、抽象数据类型、实现方式、应用场景以及性能分析，并通过代码示例帮助大家更好地理解和实践。

一、栈的概念与抽象数据类型

1.1 栈的定义

栈（Stack）是一种特殊的线性表，它只允许在表的一端进行插入和删除操作。这个特殊的端称为栈顶（Top），而另一端称为栈底（Bottom）。栈的特点是后进先出（LIFO，Last In First Out）。

1.2 栈的抽象数据类型

栈的抽象数据类型（ADT）包括以下操作：

操作	描述
push(element)	向栈顶插入一个元素
pop()	从栈顶删除一个元素并返回该元素
peek() 或 top()	查看栈顶元素而不删除
isEmpty()	判断栈是否为空
isFull()	判断栈是否已满（仅限固定大小栈）
size()	返回栈中元素的数量

1.3 栈的表示与实现

栈可以通过数组或链表实现。数组实现的栈称为顺序栈，链表实现的栈称为链栈。

顺序栈

   顺序栈使用一个固定大小的数组来存储栈中的元素，并用一个指针（通常是一个整数）来指示栈顶的位置。

链栈

   链栈使用链表来存储栈中的元素，栈顶对应链表的头节点。

1.4 栈的应用举例

• 括号匹配检查：检查括号是否正确匹配。

• 表达式求值：如中缀表达式转后缀表达式。

• 递归函数的实现：递归调用本质上使用了栈结构。

• 回溯算法：如迷宫求解。

1.5 栈的算法演示

以下是一个简单的括号匹配算法的树状图演示：

栈状态变化：
初始栈：空
输入字符：'(', 压栈 → 栈顶为 '('
输入字符：')', 弹栈 → 栈顶为空
最终栈为空 → 匹配成功

二、栈的代码实现

2.1 C语言实现

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int[MAX data_SIZE];int top;
} Stack;void initStack(Stack *s) {s->top = -1;
}int isEmpty(Stack *s) {return s->top == -1;
}int isFull(Stack *s) {return s->top == MAX_SIZE - 1;
}void push(Stack *s, int value) {if (isFull(s)) {printf("Stack is full\n");return;}s->[++datas->top] = value;
}int pop(Stack *s) {if (isEmpty(s)) {printf("Stack is empty\n");exit(1);}return s->data[s->top--];
}int peek(Stack *s) {if (isEmpty(s)) {printf("Stack is empty\n");exit(1);}return s->data[s->top];
}int main() {Stack s;initStack(&s);push(&s, 10);push(&s, 20);printf("Top element: %d\n", peek(&s));printf("Popped element: %d\n", pop(&s));return 0;
}

2.2 C++实现

​
#include <iostream>
#include <vector>
using namespace std;class Stack {
private:vector<int> data;
public:void push(int value) {data.push_back(value);}void pop() {if (!isEmpty()) {data.pop_back();}}int top() {if (!isEmpty()) {return data.back();}throw "Stack is empty";}bool isEmpty() {return data.empty();}
};int main() {Stack s;s.push(10);s.push(20);cout << "Top element: " << s.top() << endl;s.pop();cout << "Top element after pop: " << s.top() << endl;return 0;
}​

2.3 Java实现

​
import java.util.ArrayList;
import java.util.EmptyStackException;public class Stack {private ArrayList<Integer> data;public Stack() {data = new ArrayList<>();}public void push(int value) {data.add(value);}public int pop() {if (isEmpty()) {throw new EmptyStackException();}return data.remove(data.size() - 1);}public int peek() {if (isEmpty()) {throw new EmptyStackException();}return data.get(data.size() - 1);}public boolean isEmpty() {return data.isEmpty();}public static void main(String[] args) {Stack s = new Stack();s.push(10);s.push(20);System.out.println("Top element: " + s.peek());s.pop();System.out.println("Top element after pop: + " s.peek());}
}​

2.4 Python实现

​
class Stack:def __init__(self):self.data = []def push(self, value):self.data.append(value)def pop(self):if self.is_empty():raise Exception("Stack is empty")return self.data.pop()def peek(self):if self.is_empty():raise Exception("Stack is empty")return self.data[-1]def is_empty(self):return len(self.data) == 0def size(self):return len(self.data)# 示例
s = Stack()
s.push(10)
s.push(20)
print("Top element:", s.peek())
print("Popped element:", s.pop())​

三、队列的概念与抽象数据类型

3.1 队列的定义

   队列（Queue）是一种特殊的线性表，它只允许在一端进行插入操作，在另一端进行删除操作。允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。队列的特点是先进先出（FIFO，First In First Out）。

3.2 队列的抽象数据类型

队列的抽象数据类型（ADT）包括以下操作：

操作	描述
enqueue(element)	向队尾插入一个元素
dequeue()	从队头删除一个元素并返回该元素
front()	查看队头元素而不删除
isEmpty()	判断队列是否为空
isFull()	判断队列是否已满（仅限固定大小队列）
size()	返回队列中元素的数量

3.3 队列的表示与实现

队列可以通过数组或链表实现。数组实现的队列称为顺序队列，链表实现的队列称为链队列。

顺序队列

    顺序队列使用一个固定大小的数组来存储队列中的元素，并用两个指针（front 和 rear）分别指示队头和队尾的位置。为了避免空间浪费，通常使用循环队列。

链队列

   链队列使用链表来存储队列中的元素，队头对应链表的头节点，队尾对应链表的尾节点。

3.4 队列的应用举例

• 任务调度：如操作系统中的进程调度。

• 缓冲区管理：如打印机任务队列。

• 模拟场景：如银行排队系统。

• 广度优先搜索（BFS）：图的遍历算法。

3.5 队列的算法演示

以下是一个简单的银行排队系统的树状图演示：

队列状态变化：
初始队列：空
客户A到达 → 队列变为 [A]
客户B到达 → 队列变为 [A, B]
客户A办理业务 → 队列变为 [B]
客户C到达 → 队列变为 [B, C]
客户B办理业务 → 队列变为 [C]

四、队列的代码实现

4.1 C语言实现

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int front;int rear;
} Queue;void initQueueueue(Q *q) {q->front = 0;q->rear = 0;
}int isEmpty(Queue *q) {return q->front == q->rear;
}int isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}void enqueue(Queue *q, int value) {if (isFull(q)) {printf("Queue is full\n");return;}q->data[q->rear] = value;q->rear = (q->rear + 1) % MAX_SIZE;
}int dequeue(Queue *q) {if (isEmpty(q)) {printf("Queue is empty\n");exit(1);}int value = q->data[q->front];q->front = (q->front + 1) % MAX_SIZE;return value;
}int front(Queue *q) {if (isEmpty(q)) {printf("Queue is empty\n");exit(1);}return q->data[q->front];
}int main() {Queue q;initQueue(&q);enqueue(&q, 10);enqueue(&q, 20);printf("Front element: %d\n", front(&q));printf("Dequeued element: %d\n", dequeue(&q));return 0;
}

4.2 C++实现

​
#include <iostream>
#include <queue>
using namespace std;int main() {queue<int> q;q.push(10);q.push(20);cout << "Front element: " << q.front() << endl;q.pop();cout << "Front element after pop: " << q.front() << endl;return 0;
}​

4.3 Java实现

​
import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.add(10);q.add(20);System.out.println("Front element: " + q.peek());q.remove();System.out.println("Front element after remove: " + q.peek());}
}​

4.4 Python实现

​
from collections import dequeclass Queue:def __init__(self):self.data = deque()def enqueue(self, value):self.data.append(value)def dequeue(self):if self.is_empty():raise Exception("Queue is empty")return self.data.popleft()def front(self):if self.is_empty():raise Exception("Queue is empty")return self.data[0]def is_empty(self):return len(self.data) == 0def size(self):return len(self.data)# 示例
q = Queue()
q.enqueue(10)
q.enqueue(20)
print("Front element:", q.front())
print("Dequeued element:", q.dequeue())​

五、栈与队列的性能分析与应用场景对比

5.1 时间性能分析

操作	栈	队列
插入（push/enqueue）	O(1)	O(1)
删除（pop/dequeue）	O(1)	O(1)
查看顶部/头部元素	O(1)	O(1)

5.2 空间性能分析

数据结构	空间复杂度
栈（顺序栈）	O(n)
栈（链栈）	O(n)
队列（顺序队列）	O(n)
队列（链队列）	O(n)

5.3 应用场景对比

应用场景	栈适用情况	队列适用情况
括号匹配	✓
表达式求值	✓
回溯算法	✓
递归实现	✓
任务调度		✓
缓冲区管理		✓
广度优先搜索（BFS）		✓
银行排队系统		✓

六、总结

栈和队列是两种非常重要的线性表结构，它们的主要区别在于元素的插入和删除操作的位置不同。栈遵循后进先出（LIFO）原则，而队列遵循先进先出（FIFO）原则。

• 栈：适合用于括号匹配、表达式求值、递归实现等场景。

• 队列：适合用于任务调度、缓冲区管理、广度优先搜索等场景。

    两者的时间复杂度和空间复杂度都非常高效（均为O(1)和O(n)），但在不同应用场景中各有侧重。理解栈和队列的原理和实现，能够帮助我们在实际问题中选择合适的数据结构，提高程序的效率和可维护性。

希望这篇帖子能够帮助大家更好地理解和掌握栈与队列！如果有任何问题或建议，欢迎在评论区留言交流！