1. 栈的基本概念与操作
栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，最后插入的元素最先被删除。
栈的基本操作
- 初始化：创建一个空栈。
- 入栈（Push）：将一个元素压入栈顶。
- 出栈（Pop）：从栈顶删除一个元素。
- 取栈顶元素（Top）：获取栈顶元素的值，但不删除它。
- 判断是否为空：检查栈是否为空。
2. 队列的基本概念与操作
队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构，最先插入的元素最先被删除。
队列的基本操作
- 初始化：创建一个空队列。
- 入队（Enqueue）：将一个元素加入到队尾。
- 出队（Dequeue）：从队头删除一个元素。
- 取队头元素（Front）：获取队头元素的值，但不删除它。
- 判断是否为空：检查队列是否为空。
3. 栈的顺序存储结构
栈的顺序存储结构通常使用数组实现，栈顶指针 top 用于指向栈顶元素。
栈的顺序存储结构的 C++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#define MAX_SIZE 100
class Stack {
private:
int data[MAX_SIZE];
int top;
public:
Stack() : top(-1) {}
bool push(int value) {
if (top >= MAX_SIZE - 1) return false;
data[++top] = value;
return true;
}
bool pop() {
if (top == -1) return false;
top--;
return true;
}
int getTop() {
if (top == -1) return -1;
return data[top];
}
bool isEmpty() {
return top == -1;
}
void display() {
for (int i = 0; i <= top; ++i) std::cout << data[i] << " ";
std::cout << std::endl;
}
};
|
4. 队列的顺序存储结构
队列的顺序存储结构可以用循环数组实现，使用 front 和 rear 两个指针分别指向队头和队尾。
队列的顺序存储结构的 C++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
#define MAX_SIZE 100
class Queue {
private:
int data[MAX_SIZE];
int front, rear;
public:
Queue() : front(0), rear(0) {}
bool enqueue(int value) {
if ((rear + 1) % MAX_SIZE == front) return false;
data[rear] = value;
rear = (rear + 1) % MAX_SIZE;
return true;
}
bool dequeue() {
if (front == rear) return false;
front = (front + 1) % MAX_SIZE;
return true;
}
int getFront() {
if (front == rear) return -1;
return data[front];
}
bool isEmpty() {
return front == rear;
}
void display() {
int i = front;
while (i != rear) {
std::cout << data[i] << " ";
i = (i + 1) % MAX_SIZE;
}
std::cout << std::endl;
}
};
|
5. 栈的链式存储结构
栈的链式存储结构使用链表实现，每次入栈和出栈都在链表的头部操作。
栈的链式存储结构的 C++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedStack {
private:
Node* top;
public:
LinkedStack() : top(nullptr) {}
void push(int value) {
Node* newNode = new Node(value);
newNode->next = top;
top = newNode;
}
bool pop() {
if (!top) return false;
Node* temp = top;
top = top->next;
delete temp;
return true;
}
int getTop() {
return top ? top->data : -1;
}
bool isEmpty() {
return !top;
}
void display() {
Node* curr = top;
while (curr) {
std::cout << curr->data << " ";
curr = curr->next;
}
std::cout << std::endl;
}
};
|
6. 队列的链式存储结构
队列的链式存储结构使用链表实现，链表的头部作为队头，尾部作为队尾。
队列的链式存储结构的 C++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <iostream>
struct QNode {
int data;
QNode* next;
QNode(int val) : data(val), next(nullptr) {}
};
class LinkedQueue {
private:
QNode *front, *rear;
public:
LinkedQueue() : front(nullptr), rear(nullptr) {}
void enqueue(int value) {
QNode* newNode = new QNode(value);
if (!rear) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
bool dequeue() {
if (!front) return false;
QNode* temp = front;
front = front->next;
if (!front) rear = nullptr;
delete temp;
return true;
}
int getFront() {
return front ? front->data : -1;
}
bool isEmpty() {
return !front;
}
void display() {
QNode* curr = front;
while (curr) {
std::cout << curr->data << " ";
curr = curr->next;
}
std::cout << std::endl;
}
};
|
总结
- 栈：遵循 LIFO 原则，典型操作包括入栈和出栈。
- 队列：遵循 FIFO 原则，典型操作包括入队和出队。
- 顺序存储：使用数组实现，适合容量固定的情况，操作简单。
- 链式存储：使用链表实现，适合动态长度的情况，节省空间。
