- 栈与队列
- 0、物理结构与逻辑结构(了解)
- 1、栈
- 1.1 什么是栈？
- 1.2、栈的基本操作(数组)
- 1.2.1、栈的创建与初始化
- 1.2.2、入栈
- 1.2.3、弹栈
- 1.2.4、判断栈空
- 1.2.5 完整代码：
- 2、队列
- 2.1、什么是队列？
- 2.2 循环队列
- 2.2.1为什么引入循环队列？
- 2.2.2、循环队列
- 2.3、队列的基本操作（数组）
- 2.3.1、队列的创建与初始化
- 2.3.2、入队
- 2.3.3、出队
- 2.3.4、判断对空
- 2.3.5、完整代码：
- 3、STL栈
- 3.0、为什么要会STL栈？(了解)
- 3.1、堆栈操作
- 3.1.0 头文件
- 3.1.1 创建形式
- 3.1.2、栈操作基本函数：
- 3.1.3、示例演示：
- 4、STL队列
- 4.0、为什么要会STL队列？(了解)
- 4.1、队列操作
- 4.1.0、头文件
- 4.1.1、创建形式
- 4.1.2、队列操作基本函数
- 4.1.3、示例演示：
物理结构：简单来说，就是实实在在的存储结构，可分为顺序存储结构和链式存储结构。
逻辑结构：简单来说，就是人为规定逻辑，按照一定逻辑操作的存储结构，可分为线性结构和非线性结构。
常用简单分类：
| 线性结构 | 非线性结构 | |
|---|---|---|
| 逻辑结构 | 顺序表、栈、队列 | 树、图 |
| 顺序存储结构 | 链式存储结构 | |
|---|---|---|
| 物理结构 | 数组 | 链表 |
栈：栈是一种线性数据结构，规定其内部的元素满足先进后出，其中最早进入元素的位置称为栈底，最后进入元素的位置称为栈顶(top)。
数组为例：(常用)
栈底 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ top
| 3 | 4 | 2 | 8 | 9 | 5 |
|---|
链表(尾插法)为例：
1.2、栈的基本操作(数组) 1.2.1、栈的创建与初始化思想：利用top标识栈内最后一个元素的位置，本文章利用结构体进行封装栈数组和栈顶标识（top），初始化时，将top指向-1。
创建栈：
//主要代码
struct stack{
int array[10];
int top;
};
初始化：
//主要代码
void init() {
stack.top = -1;
}
1.2.2、入栈
思想：把新的元素放入栈中，只能栈顶的一侧进入，新元素作新栈顶（top++）
入栈：
//主要代码：
void push(int data) {
stack.top++;
stack.array[stack.top] = data;
}
1.2.3、弹栈
思想：从栈顶移出元素，只能栈顶的一侧弹出，出栈元素的前一个元素作为新栈顶（top–）
弹栈：
int pop() {
return stack.array[stack.top--];
}
1.2.4、判断栈空
思想：判断top是否为-1，当栈空时，返回true，否则返回false。
判空：
bool empty() {
if (stack.top == -1)
return true;
else
return false;
}
1.2.5 完整代码：
代码编译器：VS2019
//主要代码 建立StackOperation类进行封装， StackOperation.h #pragma once #includeusing namespace std; class StackOperation{ public: void init(); void push(int data); int pop(); bool empty(); private: struct stack{ int array[10]; int top; }; struct stack stack; };
//主要代码 StackOperation.cpp
#include "StackOperation.h"
void StackOperation::init() {
stack.top = -1;
}
void StackOperation::push(int data) {
stack.top++;
stack.array[stack.top] = data;
}
int StackOperation::pop() {
return stack.array[stack.top--];
}
bool StackOperation::empty() {
if (stack.top == -1)
return true;
else
return false;
}
//示例代码运行 main.cpp #include2、队列 2.1、什么是队列？#include "StackOperation.h" using namespace std; int main() { StackOperation stackOperation; stackOperation.init(); bool find = stackOperation.empty(); if (find) { cout << "top = -1" << endl; } else { cout << "top != -1" << endl; } stackOperation.push(1); find = stackOperation.empty(); if (find) { cout << "top = -1" << endl; } else { cout << "top != -1" << endl; } stackOperation.push(2); int data = stackOperation.pop(); cout << data << endl; stackOperation.pop(); find = stackOperation.empty(); if (find) { cout << "top = -1" << endl; } else { cout << "top != -1" << endl; } return 0; }
队列：队列是一种线性数据结构，不同于栈的先进后出，队列的元素规定只能先进先出，队列的出口称为对头（front）,队列的入口称为队尾（rear）。
数组为例：
对头 (front) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 队尾（rear）
| 3 | 4 | 2 | 8 | 9 | 5 |
|---|
链表为例：
2.2 循环队列 2.2.1为什么引入循环队列？如果不是循环队列，当队列不断出队时，对头左边的空间将失去作用，导致队列的容量变小，采用循环队列维持队列容量稳定。
2.2.2、循环队列循环队列：循环队列就是在逻辑上，将所开辟空间的首尾相连（实际上并没有相连，只是人为的规定）。
规定：
~~~~ a、循环队列空时，front = rear。
~~~~ b、循环队列入队时，front = (front +1) % 队列长度
~~~~ c、循环队列出队时，rear = (rear + 1) % 队列长度 （注意：队尾指针指向的位置永远空出一个位置，即队列的最大容量比实际长度小1。）
~~~~ d、循环队列满时，front = (rear + 1) %队列长度
（实际中所说的队列基本指循环队列）
2.3、队列的基本操作（数组） 2.3.1、队列的创建与初始化思想：利用front标识对头，rear标识队尾。本文章利用结构体进行封装队列数组、对头（front）和队尾（rear）。初始化时，front = rear = 0.
创建队列：
//主要代码：
struct queue {
int array[10];
int front;
int rear;
};
初始化：
//主要代码：
void init() {
queue.front = queue.rear = 0;
}
2.3.2、入队
思想： 把新的元素放在队列中，只能在队尾的位置上放入，且新放入元素的下一个位置成为新的队尾（rear=(rear+1)%存储长度）。
入队：
//主要代码：
void enter(int data) {
if ((queue.rear + 1) % 10 == arrayLength) {
cout << "queue full!" << endl;
return;
}
queue.array[queue.rear] = data; //data为入队元素
queue.rear = (queue.rear + 1) % arrayLength;
}
2.3.3、出队
思想：把新的元素移出队列，只能在对头的位置移出，且出队元素的下一个元素为新的对头（front=(front+1)%存储长度）。
出队：
//主要代码：
int departure() {
if (empty()) { //判空
cout << "queue empty!" << endl;
}
int departureData = queue.array[queue.front];
queue.front = (queue.front + 1) % arrayLength;
return departureData;
}
2.3.4、判断对空
思想：判断front是否等于rear，若等于，则为空，返回true，否则，返回false。
判空：
//主要代码：
bool QueueOperation::empty() {
if (queue.front == queue.rear) {
return true;
}
else
return false;
}
2.3.5、完整代码：
代码编译器：VS2019
//主要代码 创建QueueOperation进行封装 QueueOperation.h #pragma once #includeusing namespace std; class QueueOperation{ public: void init(); void enter(int data); int departure(); bool empty(); private: struct queue { int array[10]; int front; int rear; }; struct queue queue; int arrayLength = 10; //10为队列数组的存储长度 };
//主要代码 QueueOperation.cpp
#include "QueueOperation.h"
void QueueOperation::init() {
queue.front = queue.rear = 0;
}
void QueueOperation::enter(int data) {
if ((queue.rear + 1) % arrayLength == queue.front) {
cout << "queue full!" << endl;
return;
}
queue.array[queue.rear] = data; //data为入队元素
queue.rear = (queue.rear + 1) % arrayLength;
}
int QueueOperation::departure() {
if (empty()) {
cout << "queue empty!" << endl;
}
int departureData = queue.array[queue.front];
queue.front = (queue.front + 1) % arrayLength;
return departureData;
}
bool QueueOperation::empty() {
if (queue.front == queue.rear) {
return true;
}
else
return false;
}
//示例代码运行 main.cpp #include3、STL栈 3.0、为什么要会STL栈？(了解)#include "QueueOperation.h" using namespace std; int main() { QueueOperation queueOperation; queueOperation.init(); bool find = queueOperation.empty(); if (find) { cout << "queue empty!" << endl; } else { cout << "queue no empty!" << endl; } queueOperation.enter(1); queueOperation.enter(2); queueOperation.enter(3); cout << queueOperation.departure() << endl; cout << queueOperation.departure() << endl; find = queueOperation.empty(); if (find) { cout << "queue empty!" << endl; } else { cout << "queue no empty!" << endl; } queueOperation.departure(); find = queueOperation.empty(); if (find) { cout << "queue empty!" << endl; } else { cout << "queue no empty!" << endl; } return 0; }
在实际开发中，栈的操作具有一定的通用性，且代码在本质上也相同，最多只是栈中存储的元素类型、大小不一。因此STL栈就孕育而生，其中STL栈具有更强的通用性。
3.1、堆栈操作 3.1.0 头文件#include3.1.1 创建形式
stack<存储元素类型> 创建对象名3.1.2、栈操作基本函数：
push(T object): 将传入的对象压入栈中。
pop():弹出栈顶元素,并不会返回元素。
top():返回栈顶元素，不会弹栈。
empty(): 返回一个bool值，当栈空时返回true，否则返回false。
size():返回栈中元素的个数。
3.1.3、示例演示：代码编译器：VS2019
//示例演示 main.cpp #include4、STL队列 4.0、为什么要会STL队列？(了解)#include using namespace std; int main() { stack s1; s1.push(1); s1.push(2); s1.push(3); cout << "stack size: " << s1.size() << endl; if (s1.empty()) { cout << "stack empty!" << endl; } else { cout << "stack no empty!" << endl; } cout << s1.top() << endl; s1.pop(); cout << s1.top() << endl; s1.pop(); s1.pop(); if (s1.empty()) { cout << "stack empty!" << endl; } else { cout << "stack no empty!" << endl; } return 0; }
在实际开发中，队列的操作具有一定的通用性，且代码在本质上也相同，最多只是队列中存储的元素类型、大小不一。因此STL队列就孕育而生，其中STL队列具有更强的通用性。
4.1、队列操作 4.1.0、头文件#include4.1.1、创建形式
queue<存储元素类型> 创建对象名4.1.2、队列操作基本函数
push(): 在队尾压入新元素。
pop():删除对头元素，并且不返回值。
front():放回对头元素，并且不删除该元素。
back():返回队尾元素，并且不删除该元素。
empty(): 返回一个bool值，当队列空时返回true，否则返回false。
size(): 返回队列中元素的个数。
4.1.3、示例演示：代码编译器：VS2019
示例演示 main.cpp #include#include using namespace std; int main() { queue s1; s1.push('a'); s1.push('b'); s1.push('c'); cout << "front: " << s1.front() << endl; cout << "rear: " << s1.back() << endl; cout << "size: " << s1.size() << endl; if (s1.empty()) { cout << "queue empty!" << endl; } else { cout << "queue no empty!" << endl; } s1.pop(); s1.pop(); s1.pop(); cout << "size: " << s1.size() << endl; if (s1.empty()) { cout << "queue empty!" << endl; } else { cout << "queue no empty!" << endl; } return 0; }
