数据结构：栈、队列详解篇

一、栈

（一）栈的概念

⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。

（二）栈的实现

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。

结束语

栈和队列的分析就到这里了，如果文章可以帮助到你，那真的十分有幸，记得动手支持支持小编哦！