在学完链表后，接下来我们就开始学习栈和队列了，因为栈与队列的实现是基于链表的（也可以是数组），所以要先学链表，然后紧接着学栈与队列。
一. 栈（链表实现）
1. 栈的简介
在生活中，我们会碰到这样一种情况，在往球桶里面放球的时候，最先放进去的球，只能在最后取出。
为了模拟上述的情况，于是就出现了栈这种数据结构。
一般栈可以就行如下操作
入栈push，往栈里面存放元素。
出栈pop，取出栈的顶部元素。
清空栈pop_all，将栈里面的全部元素都出栈。
判断栈是否为空。
返回栈的顶部元素，但不出栈。
2. 栈的实现
1.入栈
void push(int i) { Node* q = new Node; q->data = i; if (tail != NULL) { q->next = tail; tail = q; } else { tail = q; q->next = NULL; } }
2.出栈
bool pop() { if (tail != NULL) { Node*q = tail; tail = tail->next; delete q; return true; } else return false; }
判断栈是否为空
bool empty() { if (tail != NULL) return false; else return true; }
返回顶部元素
int top() { if (tail != NULL) return tail->data; else return 0; }
清空栈
void pop_all() { Node * p = tail, *q; while (p->next) { q = p->next; delete p; p = q; } delete p; tail = NULL; }
完整实现
#include<iostream> using namespace std; class Node { public: int data; Node *next; }; class Stack { private: Node *tail; public: Stack() { tail = NULL; } Stack(int i) { Node *q = new Node; q->data = i; tail = q; q->next = NULL; } ~Stack() { Node * p = tail, *q; while (p) { q = p->next; delete p; p = q; } delete p; } //入栈 void push(int i) { Node* q = new Node; q->data = i; if (tail != NULL) { q->next = tail; tail = q; } else { tail = q; q->next = NULL; } } //出栈 bool pop() { if (tail != NULL) { Node*q = tail; tail = tail->next; delete q; return true; } else return false; } //返回顶部元素 int top() { if (tail != NULL) return tail->data; else return 0; } //判断栈是否为空 bool empty() { if (tail != NULL) return false; else return true; } //清空栈 void pop_all() { Node * p = tail, *q; while (p->next) { q = p->next; delete p; p = q; } delete p; tail = NULL; } };
二. 队列
1. 队列简介
在日常中，我们又会遇到另外一种非常常见的情况，那就是排队。在排队的时候，最先来的，业务就可以就先处理完。
在这种情况下，我们就使用队列这种数据结构来模拟这种情况。
队列一般可以进行的操作。
clear清空队列
isEmpty判断队列是否为空
enqueue在队列尾部加入元素
dequeue取出队列的第一个元素
firstE返回队列的第一个元素，但不删除
2. 队列的实现
完整代码，基于库中的列表
#include<list> template<class T> class Queue { private: list<T> lst; public: Queue() { } void clear() { lst.clear(); } bool isEmpty() const { return lst.empty(); } T& front() { return lst.front(); } T dequeue() { T e1 = lst.front(); lst.pop_front(); return e1; } void enqueue(const T& e1) { lst.push_back(e1); } };
三. 课后习题
将栈S中的元素的顺序倒过来
1-a 使用两个额外的栈
int main() { stack<int > q1; stack<int > q2; stack<int > q3; q1.push(1); q1.push(2); q1.push(3); q2.push(q1.top()); q1.pop(); q2.push(q1.top()); q1.pop(); q2.push(q1.top()); q1.pop(); q3.push(q2.top()); q2.pop(); q3.push(q2.top()); q2.pop(); q3.push(q2.top()); q2.pop(); q1.push(q3.top()); q3.pop(); q1.push(q3.top()); q3.pop(); q1.push(q3.top()); q3.pop(); while (!q1.empty()) { cout << q1.top(); q1.pop(); } return 0; }
1-b 使用额外的一个队列
int main() { stack<int> q; list<int> m; q.push(1); q.push(2); q.push(3); while (!q.empty()) { m.push_back(q.top()); q.pop(); } while (!m.empty()) { q.push(m.front()); m.pop_front(); } while (!q.empty()) { cout << q.top(); q.pop(); } return 0; }
1-c 使用额外的一个栈和几个额外的非数组变量
int main() { stack<int> q; stack<int> q2; q.push(1); q.push(2); q.push(3); while (!q.empty()) { q2.push(q.top()); q.pop(); } q.swap(q2); while (!q.empty()) { cout << q.top(); q.pop(); } }
使用一个额外的栈和几个额外的非数组变量，将栈S中的元素按升序排列
int main() { stack<int> q; stack<int> q2; int a=0, b=0,c = -10, min = 9999; q.push(2), q.push(5), q.push(1),q.push(4),q.push(7),q.push(10),q.push(8),q.push(3); for (int i = 0; i < 7; i++) { min = 999; while (!q.empty()) { if (q.top() == c) break; if (q.top() < min) min = q.top(); q2.push(q.top()); q.pop(); } c =min; q.push(min); while (!q2.empty()) { if (q2.top() == min) { q2.pop(); continue; } q.push(q2.top()); q2.pop(); } b = 0; } while (!q.empty()) { cout << q.top()<<" "; q.pop(); } return 0; }
将栈S1中的元素转换到栈S2中，使S2中元素的顺序与S1中元素的顺序相同
3-a 使用一个额外的栈
int main() { stack<int> S1; stack<int> S2; stack<int> q; S1.push(2), S1.push(3), S1.push(4), S1.push(5); while (!S1.empty()) { q.push(S1.top()); S1.pop(); } while (!q.empty()) { S2.push(q.top()); q.pop(); } while (!S2.empty()) { cout << S2.top() << " "; S2.pop(); } return 0; }
3-b 不使用额外的栈，只使用几个额外的非数组变量
int main() { stack<int> S1, S2; int a, b=0, c = 1, d; S1.push(1); S1.push(2); S1.push(3); S1.push(4); a = S1.size(); while (a) { // 写出 i<S1.size() - 1 会出现错误 for (int i = 0; i <a - c; i++) { S2.push(S1.top()); S1.pop(); } d = S1.top(); S1.pop(); for (int i = 0; i < 3-b; i++) { S1.push(S2.top()); S2.pop(); } S2.push(d); b++; a--; } while (!S2.empty()) { cout << S2.top() << " "; S2.pop(); } return 0; }
使用额外的非数组变量及下面的条件，将队列中的所有元素排序
5-a 两个额外的队列
int main() { queue<int> q1 , q2, q3; q1.push(4), q1.push(1), q1.push(7), q1.push(10), q1.push(2), q1.push(6), q1.push(8); int min; int a = q1.size(); for (int i = 0; i < a; i++) { min = 999; while (!q1.empty()) { if (q1.front() < min) { min = q1.front(); } q2.push(q1.front()); q1.pop(); } while (!q2.empty()) { if (q2.front() == min) { q2.pop(); continue; } q1.push(q2.front()); q2.pop(); } q3.push(min); } while (!q3.empty()) { cout << q3.front()<<" " ; q3.pop(); } return 0; }
以上就是栈和队列的大部分内容。
ps：以上知识学习于《C++数据结构与算法》Adam Drozdek 著, 徐丹，吴伟敏 译。
Thank for your reading ！！！
公众号：FPGA之旅
