一、栈的定义
队列是一种先进先出(FIRST IN FIRST OUT)的线性表首先进行栈的抽象类定义：
template<class elemtype> //栈的抽象类 class queue{ public: virtual isempty()const=0;//判空 virtual void enQueue(const elemtype& x)=0;//入队 virtual elemtype deQueue()=0;//出队 virtual elemtype head()=0;//取队头元素 virtual ~queue()=0;//虚析构 };
二、顺序队列完整实现
栈的操作仅在栈顶进行，而队列既有在队头也有在队尾操作，所以值得讨论队头队尾设在哪里的问题。
①队头固定
假设去超市买东西排队付款，服务台所在的位置固定
设一个队尾指针rear，判空的方法是rear=-1，取队头元素就是elem[0]，入队就是elem[++rear]=x,出队则需将后面len-1个元素往前覆盖，此时时间复杂度为O(n)，出队的效率不理想
②队头不固定
假设服务员服务周到，每次服务完一个顾客后，走到下一个顾客前面进行服务
为了使出队有更好的时间效能，我们可以设队头指针front和队尾指针rear，front指向第一个元素前面的一个元素，那队列初始化时，front=rear=-1，入队就是elem[++rear]=x,出队就是x=elem[++front],判空的依据是front==rear，取队头就是elem[front+1]，时间复杂度都是O（1)。但是显然②都存在一个很大的问题就是空间利用率低，比如queue的容量是MAXSIZE，而如果入队后执行了出队操作后，直至rear=MAXSIZE-1，那就无法在入队了，而此时数组前面还有未利用空间，所以想到一种改进方法就是循环队列
③循环队列
想要实现循环，不难想到取模的方法，入队就是rear=(rear+1)%Maxsize,elem[rear]=x,出队就是x=elem[front],front=(front+1)%Maxsize
在创建队列时我们可以将rear和front初始化为0
但此时发现，队空和队满都是rear==front无法区分，因此我们空出一块空间(规定front位置不能放元素)，来避免这个问题，那这个时候队满就是(rear+1)%maxsize==front,队空就是rear==front
顺序栈性能分析
//顺序队列
template<class elemtype>
class SeqQueue :public Queue<elemtype>
{
private:
elemtype* elem;//数组基地址
int maxsize; //最大容量
int front;//队头指针
int rear;//队尾指针
void doubleSpace();//扩容工具函数
public:
SeqQueue(int initSize = 10);
bool isempty()const;//判空
void enQueue(const elemtype& x);//入栈
elemtype deQueue();//出栈
elemtype top()const; //取队头元素
~SeqQueue();
};
//扩容函数实现
template<class elemtype>
void SeqQueue<elemtype>::doubleSpace()
{
elemtype* tmp = elem; //保存副本
elem = new elemtype[2 * maxsize];
//队列已满时，队中有maxsize-1个元素,rear在front后面一个位置
//复制副本,将所有元素放在队头
for (int i = 1; i < maxsize; ++i)
{
elem[i] = tmp[(rear + i) % maxsize];
}
maxsize *= 2;
front = 0;
rear = maxsize - 1;
delete[] tmp; //删除副本
}
//构造函数和析构函数的实现
template<class elemtype>
SeqQueue<elemtype>::SeqQueue(int initSize) //默认参数定义时隐藏
{
maxsize = initSize; //确定队列的容量
elem = new elemtype[maxsize]; //开辟栈空间
front = rear = 0; //初始化队头队尾
}
template<class elemtype>
SeqQueue<elemtype>::~SeqQueue()
{
if (elem)
{
delete[] elem; //销毁栈空间
elem = nullptr;
}
}
//队列判空
template<class elemtype>
bool SeqQueue<elemtype>::isempty()const
{
return front == rear;
}
//入队
template<class elemtype>
void SeqQueue<elemtype>::enQueue(const elemtype& x)
{
if ((rear + 1) % maxsize == front))//队列满则扩容
{
doubleSpace();
}
else { //后移队尾指针，插入元素
rear = (rear + 1) % maxsize;
elem[rear] = x;
}
}
//出队
template<class elemtype>
elemtype SeqQueue<elemtype>::deQueue()
{
if (isempty(*this)) cout << "当前队空!";
else { //后移队头指针，出队
front = (front + 1) % maxsize;
return elem[front];
}
}
//取队头元素
template<class elemtype>
elemtype SeqQueue<elemtype>::top()const
{
if (isempty(*this)) cout << "当前队空!";
else {
return elem[(front+1)%maxsize]; //返回栈顶元素
}
}三、链队完整实现
//链接队列
template<class elemtype>
class LinkQueue :public stack<elemtype>
{
private:
//将结点作为内置结构体类型
struct node {
elemtype data;
node* next;
//同样设置构造函数和析构函数
node(const elemtype& x, node* N = nullptr) {
data = x;
next = N;
}
node():next(nullptr) {};
~node() {};
};
node* front; //队头指针
node* rear; //队尾指针
public:
LinkQueue();
bool isempty()const;//判空
void enQueue(const elemtype& x);//入队
elemtype deQueue();//出队
elemtype top()const; //取队头元素
~LinkQueue();
};
//构造函数和析构函数的实现
template<class elemtype>
LinkQueue<elemtype>::LinkQueue()
{
//队空就是队头、队尾指针挂空
front = rear = nullptr;
}
template<class elemtype>
LinkQueue<elemtype>::~LinkQueue()
{
node* tmp;
if (front)
{
//删除三部曲，定位，移动，删除
tmp = front;
front= front->next;
delete tmp;
}
}
//队列判空
template<class elemtype>
bool LinkQueue<elemtype>::isempty()const
{
return front == nullptr;
}
//入队
template<class elemtype>
void LinkQueue<elemtype>::enQueue(const elemtype& x)
{
if (isempty(*this)) //队空则申请空间
front = rear = new node(x);
else {
node* tmp = new(x);
rear->next = tmp;
rear = tmp;
}
}
//出队
template<class elemtype>
elemtype LinkQueue<elemtype>::deQueue()
{
if (isempty(*this)) cout << "当前队列空" << endl;
else {
elemtype value = front->data;
node* tmp = front;
front = front->next;
delete tmp;
return value;
}
}
//取队头元素
template<class elemtype>
elemtype LinkQueue<elemtype>::top()const
{
if (isempty(*this)) cout << "当前队列空" << endl;
else {
return front->data;
}
} 也可使用单循环链表，只需要一个rear队尾指针即可，入队就是在rear后面插入一个结点，出队就是删除rear后面的结点，rear的下一个结点即front
四、STL中的队列
在STL中，队列是一个容器适配器（借助于其他容list/deque存储元素）
定义队列的形式 queue<ElemType，Container<ElemType>>,其中Container默认为deque
使用栈首先需要包含头文件<queue>
STL的队列提供6个函数：入队push、出队pop、队头front、队尾back、判空empty、队长size
五、leetcode实战
1.leetcode 232 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty- 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）进阶：
- 你能否实现每个操作均摊时间复杂度为
O(1)的队列？换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能花费较长时间。
class MyQueue { private: //创建一个入栈和一个出栈来模拟队列功能 stack<int> stack_in; stack<int> stack_out; public: MyQueue() { } void push(int x) { stack_in.push(x); } int pop() { //出栈不空，此时队头元素就在出栈顶 int value; if(!stack_out.empty()) { value=stack_out.top(); stack_out.pop(); } //出栈空，则将入栈元素全部转移到出栈中，并删除栈顶元素 else{ while(!stack_in.empty()) { stack_out.push(stack_in.top()); stack_in.pop(); } value=stack_out.top(); stack_out.pop(); } return value; } int peek() { //若出栈空，则此时队头在入栈尾部，先将入栈元素全部转移到出栈中 if(stack_out.empty()){ int value=pop(); stack_out.push(value); //把弹出的元素放回去 } return stack_out.top(); } bool empty() { return stack_in.empty()&&stack_out.empty(); } };
2.leetcode 225 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False提示：
1 <= x <= 9- 最多调用
100次push、pop、top和empty- 每次调用
pop和top都保证栈不为空进阶：你能否仅用一个队列来实现栈。
分析：作为上道题的姐妹题，在上道题中我们使用了两个栈来实现队列的功能，那是否要用两个队列实现栈的功能呢？其实队列相比栈更加灵活，仅仅一个队列就能模拟栈。我们可以把队头当栈顶，这时候插入就需要多次移动操作，也可以把队尾当栈顶，这时候删除需要多次移动操作，考虑到插入的频率更高，我们采用后者。而且利用queue
class MyStack { public: queue<int> que; /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { que.push(x); } /** Removes the element on top of the stack and returns that element. */ int pop() { int size = que.size(); size--; while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部 que.push(que.front()); que.pop(); } int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了 que.pop(); return result; } /** Get the top element. */ int top() { return que.back(); } /** Returns whether the stack is empty. */ bool empty() { return que.empty(); } };
3.leetcode 239 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
提示：
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
deque：STL中stack、queue的默认底层容器，支持前端和后端操作
实际上，deque 既可以充当队列（queue）也可以充当栈（stack）。
deque 是 C++ 标准库中的双端队列（double-ended queue）容器，支持在两端进行元素的插入和删除操作。由于其能够在队列的前端和后端执行各种操作，因此它可以用作队列（先进先出）或栈（后进先出）。
如果你想使用 deque 作为队列，可以使用它的 push_back() 和 pop_front() 方法来进行入队和出队操作。如果你想使用它作为栈，可以使用 push_back() 和 pop_back() 方法来进行入栈和出栈操作。
示例代码：
#include <iostream> #include <deque> int main() { std::deque<int> myDeque; // 作为队列使用 myDeque.push_back(1); myDeque.push_back(2); std::cout << "Front of queue: " << myDeque.front() << std::endl; myDeque.pop_front(); // 作为栈使用 myDeque.push_back(3); myDeque.push_back(4); std::cout << "Top of stack: " << myDeque.back() << std::endl; myDeque.pop_back(); return 0; }这段代码中，我们展示了如何利用 deque 来实现队列和栈的功能。deque 的灵活性使得它在很多场景下都是一个非常有用的容器。
分析：非常经典的单调队列的题目，所谓的单调队列，就是维护队列中元素具有一定的大小关系。
首先滑动窗口移动的特点是移出一个元素，移入一个元素，符合队列的特性。
我们想自定义队列的规则，就是对于队列的push和pop函数进行改写，使最大值始终维护在一个易于获取的位置——队头。
push:
假设当前需要push的元素为x。
若队头元素小于等于x，则先将x前面的元素全部弹出（若是之后需要弹出的元素，我们先提前弹出；位于x的前面，又不是最大值，那必然不可能作为x之后的窗口中的最大值）；
若队头元素大于x，则将x插入
pop：
假设当前需要pop的元素为y。
若队头元素等于y，那么pop队头元素；
若队头元素大于y，则这个时候y应已经被提前弹出了，无需操作
总体窗口移动流程：
先把前k个元素push，得到一个最大值
接下来就是要移动窗口，i from k to nums.size（）-1，push nums[i],pop[i-k]，每次取一个最大值放进最终答案数组。