数据结构：栈、队列详解篇
数据结构：栈、队列详解篇
- 一、栈
- （一）栈的概念
- （二）栈的实现
- 1、结构定义
- 2、功能实现
- （1）栈的初始化
- （2）栈的销毁
- （3）栈的扩容
- （4）压栈
- （5）出栈
- （6）取栈顶元素、判空、栈的大小
- (三）例题分析
- 1、有效的括号
- 题目分析
- 二、队列
- （一）队列的概念
- （二）队列的实现
- 1、结构定义
- 2、功能实现
- （1）队列结点生成
- （2）队列初始化
- （3）入队列
- （4）出队列
- （5）队列的销毁
- （6）队列判空、取队列首元素、尾元素、数据个数
- （三）例题分析
- 1、用栈实现队列
- 题目分析
- 2、用队列实现栈
- 题目分析
- 3、设计循环队列
- 结束语
一、栈
（一）栈的概念
⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。
（二）栈的实现
1、结构定义
在定义栈时，我们下面用数组实现栈，用到 typedef 可以使得栈的数据类型更广。
typedef int StackDataType;
typedef struct Stack {
StackDataType* data;
int capacity;
int top;
}Stack;
2、功能实现
（1）栈的初始化
我们传进来的栈是 &（变量）的形式，因此这里不用使用 malloc 为栈开辟空间。
void StackInit(Stack* pS) {
assert(pS);
pS->data = NULL;
pS->capacity = 0;
pS->top = 0;
return;
}
（2）栈的销毁
只用对 data 进行释放即可，因为栈本身没有进行动态空间的申请，就不用释放，但是要记得把变量的 capacity 和 top 重置为 0
void StackDestroy(Stack* pS) {
assert(pS);
if (pS->data) {
free(pS->data);
pS->data = NULL;
}
pS->capacity = pS->top = 0;
return;
}
（3）栈的扩容
利用 realloc 进行扩容即可，三目运算符记得栈初始化大小为 0
void StackCheckCapacity(Stack* pS) {
assert(pS);
if (pS->capacity == pS->top) {
int capacity = pS->capacity == 0 ? 4 : 2 * pS->capacity;
StackDataType* s = (StackDataType*)realloc(pS->data, sizeof(StackDataType) * capacity);
if (s == NULL) {
perror("realloc fail!");
exit(1);
}
pS->data = s;
pS->capacity = capacity;
}
return;
}
（4）压栈
检查容量后压栈
void StackPush(Stack* pS, StackDataType x) {
assert(pS);
StackCheckCapacity(pS);
pS->data[pS->top] = x;
pS->top += 1;
return;
}
（5）出栈
直接 -1 即可，空间还再只是不可非法访问。
void StackPop(Stack* pS) {
assert(pS);
pS->top -= 1;
return;
}
（6）取栈顶元素、判空、栈的大小
这三个操作比较简单，但是记得断言一下指针是否为空，或者栈是否为空
bool StackEmpty(Stack* pS) {
assert(pS);
return pS->top == 0;
}
int StackSize(Stack* pS) {
assert(pS);
return pS->capacity;
}
//取栈顶元素
StackDataType StackTop(Stack* s) {
assert(s);
assert(!StackEmpty(s));
return s->data[s->top - 1];
}
(三）例题分析
1、有效的括号
https://leetcode.cn/problems/valid-parentheses/description/
题目分析
采用栈来解决，如果是左括号进栈，右括号出栈，最后判断栈是否为空，
下面直接用STL提供的stack来实现
class Solution {
public:
bool isValid(string s) {
stack<char> st;
int i = 0;
while (s[i]) {
if (s[i] == '{' || s[i] == '[' || s[i] == '(') {
st.push(s[i]);
} else if (!st.empty() && (s[i] == '}' && st.top() == '{' ||
s[i] == ']' && st.top() == '[' ||
s[i] == ')' && st.top() == '(')) {
st.pop();
} else {
return false;
}
i += 1;
}
if (st.empty())
return true;
return false;
}
};
二、队列
（一）队列的概念
概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出的性质
⼊队列：进⾏插⼊操作的⼀端称为队尾
出队列：进⾏删除操作的⼀端称为队头
（二）队列的实现
1、结构定义
我们下面用链表来实现队列，需要用到两个结构体定义结点结构和队列结构
typedef int QueueDataType;
typedef struct QueueNode {
QueueDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
QueueNode* head;
QueueNode* tail;
int size;
}Queue;
2、功能实现
（1）队列结点生成
用队列的指针来接收动态内存申请的空间
QueueNode* BuyNode(QueueDataType data) {
QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));
if (p == NULL) {
perror("malloc fail!");
exit(1);
}
p->data = data;
p->next = NULL;
return p;
}
（2）队列初始化
void QueueInit(Queue* pQue) {
assert(pQue);
pQue->head = pQue->tail = NULL;
pQue->size = 0;
return;
}
（3）入队列
记得处理队列结点为空的情况
void QueuePush(Queue* pQue, QueueDataType data) {
assert(pQue);
QueueNode* node = BuyNode(data);
if (pQue->head == NULL) {
pQue->head = pQue->tail = node;
}
else {
pQue->tail->next = node;
pQue->tail = node;
}
pQue->size += 1;
return;
}
（4）出队列
元素个数为 1 时，需要特殊处理。
void QueuePop(Queue* pQue) {
assert(pQue);
assert(!QueueEmpty(pQue));
pQue->size -= 1;
if (pQue->head == pQue->tail) {
free(pQue->head);
pQue->head = pQue->tail = NULL;
return;
}
QueueNode* node = pQue->head;
pQue->head = pQue->head->next;
free(node);
node = NULL;
return;
}
（5）队列的销毁
遍历队列结点后销毁，然后记得将指针置空，将元素数量置为 0
void QueueDestroy(Queue* pQue) {
assert(pQue);
if (QueueEmpty(pQue)) return;
QueueNode* p = pQue->head;
while (p) {
QueueNode* node = p;
p = p->next;
free(node);
}
pQue->head = pQue->tail = NULL;
pQue->size = 0;
return;
}
（6）队列判空、取队列首元素、尾元素、数据个数
代码难度不大，一样断言判断传入的数据是不是有效数据，以及+队列是否为空
bool QueueEmpty(Queue* pQue) {
assert(pQue);
return pQue->head == NULL && pQue->tail == NULL;
}
QueueDataType QueueFront(Queue* pQue) {
assert(pQue);
assert(!QueueEmpty(pQue));
return pQue->head->data;
}
QueueDataType QueueBack(Queue* pQue) {
assert(pQue);
assert(!QueueEmpty(pQue));
return pQue->tail->data;
}
int QueueSize(Queue* pQue) {
assert(pQue);
return pQue->size;
}
（三）例题分析
1、用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/
题目分析
创建两个栈 pushS 和 popS
push 操作直接往 pushS 里面压入元素
pop 操作弹出 popS 的栈顶元素。如果popS里面没有元素，就将pushS 的元素放进popS，再弹出栈顶元素
class MyQueue {
public:
stack<int> pushS;
stack<int> popS;
MyQueue() {}
void push(int x) {
pushS.push(x);
}
int pop() {
if(popS.empty()){
while(pushS.size()){
int top = pushS.top();
popS.push(top);
pushS.pop();
}
}
int ret = popS.top();
popS.pop();
return ret;
}
int peek() {
if(popS.empty()){
while(pushS.size()){
int top = pushS.top();
popS.push(top);
pushS.pop();
}
}
return popS.top();
}
bool empty() {
return popS.empty() && pushS.empty();
}
};
小结：队列的两道题涉及栈和队列的相互转换，同时可以用来提升思维能力
2、用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
题目分析
用两个队列实现栈， 两个队列中，一个队列设置为空，另外一个放元素。
push 操作直接往有元素的队列放入元素即可。
pop 操作要先将有元素的队列 size - 1 个元素依次出队列，按照出队列顺序进入另外一个队列，然后弹出并返回最后一个元素即可。
top 操作直接返回有元素队列的最后一个元素。
class MyStack {
public:
queue<int> q1;
queue<int> q2;
MyStack() {}
void push(int x) {
if (!q1.empty()) {
q1.push(x);
} else {
q2.push(x);
}
}
int pop() {
queue<int> *emp = &q1;
queue<int> *nemp = &q2;
if (!q1.empty()) {
emp = &q2, nemp = &q1;
}
int n = nemp->size() - 1;
while (n--) {
emp->push(nemp->front());
nemp->pop();
}
int ret = nemp->front();
nemp->pop();
return ret;
}
int top() {
queue<int> *emp = &q1;
queue<int> *nemp = &q2;
if (!q1.empty()) {
emp = &q2, nemp = &q1;
}
return nemp->back();
}
bool empty() { return q1.empty() && q2.empty(); }
};
小结：这里不要错误的直接用引用取别名，emp 和 nemp 不然后面不可以修改
3、设计循环队列
https://leetcode.cn/problems/design-circular-queue/description/
class MyCircularQueue {
public:
int* data;
int capacity;
int tail;
int head;
MyCircularQueue(int k) {
data = (int*)malloc(sizeof(int) * (k + 1));
capacity = k + 1;
head = tail = 0;
}
bool enQueue(int value) {
if(isFull()) return false;
data[tail] = value;
if((tail + 1) == capacity) tail = 0;
else tail++;
return true;
}
bool deQueue() {
if(isEmpty()) return false;
if((head + 1) == capacity) head = 0;
else head++;
return true;
}
int Front() {
if(isEmpty()) return -1;
return data[head];
}
int Rear() {
if(isEmpty()) return -1;
int ind = tail - 1;
if(tail == 0) ind = capacity - 1;
return data[ind];
}
bool isEmpty() {
return head == tail;
}
bool isFull() {
return ((tail + 1) % capacity) == head;
}
};
小结：设计循环队列时，可以在申请 data 空间时多申请一份，这样就不用再创建另外的变量。另外，注意在 head tail 指针在 ++ 过程中，如果越界了要将位置移动到 0。
结束语
栈和队列的分析就到这里了，如果文章可以帮助到你，那真的十分有幸，记得动手支持支持小编哦！
