• 数据结构——队列

    一、栈的定义


    队列是一种先进先出(FIRST IN FIRST OUT)的线性表

    首先进行栈的抽象类定义：

    1. template<class elemtype>
    2. //栈的抽象类
    3. class  queue{
    4.     public:
    5.         virtual isempty()const=0;//判空
    6.         virtual void enQueue(const elemtype& x)=0;//入队
    7.         virtual elemtype deQueue()=0;//出队
    8.         virtual elemtype head()=0;//取队头元素
    9.         virtual ~queue()=0;//虚析构    
    10. };

     二、顺序队列完整实现

    栈的操作仅在栈顶进行，而队列既有在队头也有在队尾操作，所以值得讨论队头队尾设在哪里的问题。

    ①队头固定

    假设去超市买东西排队付款，服务台所在的位置固定

    设一个队尾指针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

    顺序栈性能分析

    1. //顺序队列
    2. template<class elemtype>
    3. class SeqQueue :public Queue
    4. {
    5. private:
    6. 	elemtype* elem;//数组基地址
    7. 	int maxsize; //最大容量
    8. 	int front;//队头指针
    9. 	int rear;//队尾指针
    10. 	void doubleSpace();//扩容工具函数
    11. public:
    12. 	SeqQueue(int initSize = 10);
    13. 	bool isempty()const;//判空
    14. 	void enQueue(const elemtype& x);//入栈
    15. 	elemtype deQueue();//出栈
    16. 	elemtype top()const; //取队头元素
    17. 	~SeqQueue();
    18. };
    19. //扩容函数实现
    20. template<class elemtype>
    21. void SeqQueue::doubleSpace()
    22. {
    23. 	elemtype* tmp = elem; //保存副本
    24. 	elem = new elemtype[2 * maxsize];
    25. 	//队列已满时，队中有maxsize-1个元素,rear在front后面一个位置
    26. 	//复制副本,将所有元素放在队头
    27. 	for (int i = 1; i < maxsize; ++i)
    28. 	{
    29. 		elem[i] = tmp[(rear + i) % maxsize];
    30. 	}
    31. 	maxsize *= 2;
    32. 	front = 0;
    33. 	rear = maxsize - 1;
    34. 	delete[] tmp; //删除副本
    35. }
    36. //构造函数和析构函数的实现
    37. template<class elemtype>
    38. SeqQueue::SeqQueue(int initSize) //默认参数定义时隐藏
    39. {
    40. 	maxsize = initSize; //确定队列的容量
    41. 	elem = new elemtype[maxsize]; //开辟栈空间
    42. 	front = rear = 0; //初始化队头队尾
    43. }
    44.  
    45. template<class elemtype>
    46. SeqQueue::~SeqQueue()
    47. {
    48. 	if (elem)
    49. 	{
    50. 		delete[] elem; //销毁栈空间
    51. 		elem = nullptr;
    52. 	}
    53. }
    54.  
    55. //队列判空
    56. template<class elemtype>
    57. bool SeqQueue::isempty()const
    58. {
    59. 	return front == rear;
    60. }
    61.  
    62. //入队
    63. template<class elemtype>
    64. void SeqQueue::enQueue(const elemtype& x)
    65. {
    66. 	if ((rear + 1) % maxsize == front))//队列满则扩容
    67. 	{
    68. 		doubleSpace();
    69. 	}
    70. 	else {  //后移队尾指针，插入元素
    71. 		rear = (rear + 1) % maxsize;
    72. 		elem[rear] = x;
    73. 	}
    74. }
    75.  
    76. //出队
    77. template<class elemtype>
    78. elemtype SeqQueue::deQueue()
    79. {
    80. 	if (isempty(*this)) cout << "当前队空!";
    81. 	else {  //后移队头指针，出队
    82. 		front = (front + 1) % maxsize;
    83. 		return elem[front];
    84. 	}
    85. }
    86.  
    87. //取队头元素
    88. template<class elemtype>
    89. elemtype SeqQueue::top()const
    90. {
    91. 	if (isempty(*this)) cout << "当前队空!";
    92. 	else {
    93. 		return elem[(front+1)%maxsize]; //返回栈顶元素
    94. 	}
    95. }

    三、链队完整实现 

    1. //链接队列
    2. template<class elemtype>
    3. class LinkQueue :public stack
    4. {
    5. private:
    6. 	//将结点作为内置结构体类型
    7. 	struct node {
    8. 		elemtype data;
    9. 		node* next;
    10. 		//同样设置构造函数和析构函数
    11. 		node(const elemtype& x, node* N = nullptr) {
    12. 			data = x;
    13. 			next = N;
    14. 		}
    15. 		node():next(nullptr) {};
    16. 		~node() {};
    17. 	};
    18. 	node* front; //队头指针
    19. 	node* rear; //队尾指针
    20. public:
    21. 	LinkQueue();
    22. 	bool isempty()const;//判空
    23. 	void enQueue(const elemtype& x);//入队
    24. 	elemtype deQueue();//出队
    25. 	elemtype top()const; //取队头元素
    26. 	~LinkQueue();
    27. };
    28.  
    29. //构造函数和析构函数的实现
    30. template<class elemtype>
    31. LinkQueue::LinkQueue()
    32. {
    33. 	//队空就是队头、队尾指针挂空
    34. 	front = rear = nullptr;
    35. }
    36.  
    37. template<class elemtype>
    38. LinkQueue::~LinkQueue()
    39. {
    40. 	node* tmp;
    41. 	if (front)
    42. 	{
    43. 		//删除三部曲，定位，移动，删除
    44. 		tmp = front;
    45. 		front= front->next;
    46. 		delete tmp;
    47. 	}
    48. }
    49.  
    50. //队列判空
    51. template<class elemtype>
    52. bool LinkQueue::isempty()const
    53. {
    54. 	return front == nullptr;
    55. }
    56.  
    57. //入队
    58. template<class elemtype>
    59. void LinkQueue::enQueue(const elemtype& x)
    60. {
    61. 	if (isempty(*this)) //队空则申请空间
    62. 		front = rear = new node(x);
    63. 	else {
    64. 		node* tmp = new(x);
    65. 		rear->next = tmp;
    66. 		rear = tmp;
    67. 	}
    68. 	
    69. }
    70.  
    71. //出队
    72. template<class elemtype>
    73. elemtype LinkQueue::deQueue()
    74. {
    75. 	if (isempty(*this)) cout << "当前队列空" << endl;
    76. 	else {
    77. 		elemtype value = front->data;
    78. 		node* tmp = front;
    79. 		front = front->next;
    80. 		delete tmp;
    81. 		return value;
    82. 	}
    83.  
    84. }
    85.  
    86. //取队头元素
    87. template<class elemtype>
    88. elemtype LinkQueue::top()const
    89. {
    90. 	if (isempty(*this)) cout << "当前队列空" << endl;
    91. 	else {
    92. 		return front->data;
    93. 	}
    94. }

     也可使用单循环链表，只需要一个rear队尾指针即可，入队就是在rear后面插入一个结点，出队就是删除rear后面的结点，rear的下一个结点即front

    四、STL中的队列


    在STL中，队列是一个容器适配器（借助于其他容list/deque存储元素）

    定义队列的形式 queue<ElemType，Container>,其中Container默认为deque

    使用栈首先需要包含头文件

    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) ，即使其中一个操作可能花费较长时间。
    1. class MyQueue {
    2.  private:
    3.  //创建一个入栈和一个出栈来模拟队列功能
    4.   stack<int> stack_in;
    5.    stack<int> stack_out;
    6.    
    7.        
    8. public:
    9.     MyQueue() {
    10.           
    11.     }
    12.     
    13.     void push(int x) {
    14.           stack_in.push(x);
    15.     }
    16.     
    17.     int pop() {
    18.         //出栈不空，此时队头元素就在出栈顶
    19.         int value;
    20.          if(!stack_out.empty())
    21.          {
    22.              value=stack_out.top();
    23.              stack_out.pop();
    24.          }
    25.          //出栈空，则将入栈元素全部转移到出栈中，并删除栈顶元素
    26.          else{
    27.              while(!stack_in.empty())
    28.             {
    29.                 stack_out.push(stack_in.top());
    30.                 stack_in.pop();
    31.             }
    32.             value=stack_out.top();
    33.             stack_out.pop();
    34.          }
    35.          return value;
    36.  
    37.     }
    38.     
    39.     int peek() {
    40.          //若出栈空，则此时队头在入栈尾部，先将入栈元素全部转移到出栈中
    41.          if(stack_out.empty()){
    42.              int value=pop();
    43.              stack_out.push(value); //把弹出的元素放回去
    44.          }
    45.          return stack_out.top();
    46.     }
    47.     
    48.     bool empty() {
    49.            return stack_in.empty()&&stack_out.empty();
    50.     }
    51.  
    52. };

    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

    1. class MyStack {
    2. public:
    3.     queue<int> que;
    4.     /** Initialize your data structure here. */
    5.     MyStack() {
    6.  
    7.     }
    8.     /** Push element x onto stack. */
    9.     void push(int x) {
    10.         que.push(x);
    11.     }
    12.     /** Removes the element on top of the stack and returns that element. */
    13.     int pop() {
    14.         int size = que.size();
    15.         size--;
    16.         while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
    17.             que.push(que.front());
    18.             que.pop();
    19.         }
    20.         int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
    21.         que.pop();
    22.         return result;
    23.     }
    24.  
    25.     /** Get the top element. */
    26.     int top() {
    27.         return que.back();
    28.     }
    29.  
    30.     /** Returns whether the stack is empty. */
    31.     bool empty() {
    32.         return que.empty();
    33.     }
    34. };

    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() 方法来进行入栈和出栈操作。

    示例代码：

    1. #include 
    2. #include 
    3.  
    4. int main() {
    5.     std::deque<int> myDeque;
    6.  
    7.     // 作为队列使用
    8.     myDeque.push_back(1);
    9.     myDeque.push_back(2);
    10.     std::cout << "Front of queue: " << myDeque.front() << std::endl;
    11.     myDeque.pop_front();
    12.  
    13.     // 作为栈使用
    14.     myDeque.push_back(3);
    15.     myDeque.push_back(4);
    16.     std::cout << "Top of stack: " << myDeque.back() << std::endl;
    17.     myDeque.pop_back();
    18.  
    19.     return 0;
    20. }

    这段代码中，我们展示了如何利用 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]，每次取一个最大值放进最终答案数组。

  • 相关阅读:
    【MindSpore易点通】数据处理之Numpy数组的使用
    服务器防漏扫，主机加固方案来解决
    深度学习微调
    pytorch_quantization安装
    leetcode:152. 乘积最大子数组
    技术分享 | Web测试方法与技术实战演练
    SpringMVC入门
    人体骨骼点检测：自顶向下（部分理论）
    QT -- 多线程 —— moveToThread
    Qt使用QListWidget实现自定义Item效果
  • 原文地址：https://blog.csdn.net/2301_79376014/article/details/136579205