【十七】【C++】stack的简单实现、queue的常见用法以及用queue实现stack

stack的简单实现

#include <deque>
#include <iostream>
using namespace std;
namespace Mystack {
    template<class T, class Container = std::deque<T>>
    class stack {
        public:
            stack()
                : _c()
            {}

            void push(const T& data) {
                _c.push_back(data);
            }

            void pop() {
                if (empty()) {
                    return;
                }

                _c.pop_back();
            }

            size_t size()const {
                return _c.size();
            }

            bool empty()const {
                return _c.empty();
            }

            T& top() {
                return _c.back();
            }

            const T& top()const {
                return _c.back();
            }
        private:
            Container _c;
    };
 }

这段代码定义了一个模板类stack，位于命名空间Mystack中。它是对C++标准库容器的一种适配，使其表现得像一个栈（Stack）。栈是一种后进先出（Last In, First Out，LIFO）的数据结构，这意味着最后被加入栈的元素会是第一个被移除的。这个自定义栈通过内部封装了一个容器（默认为std::deque<T>）来实现其功能。

类模板参数

T：栈中存储的元素类型。

Container：底层容器类型，用于实际存储栈中的元素，默认为std::deque<T>。deque（双端队列）是一个允许在两端进行插入和删除操作的序列容器。

成员函数

构造函数 stack()：初始化一个空的栈实例。

push(const T& data)：向栈顶添加一个元素。这里使用的是底层容器的push_back方法，表示元素总是被添加到容器的末尾，符合栈的LIFO特性。

pop()：移除栈顶元素。这里使用的是底层容器的pop_back方法，从容器末尾移除元素。如果栈为空（即容器为空），则pop操作不执行任何操作。

size()const：返回栈中元素的数量，即底层容器中元素的数量。

empty()const：检查栈是否为空。如果底层容器为空，这个方法返回true；否则返回false。

top() 和 const T& top()const：返回对栈顶元素的引用。非const版本允许修改栈顶元素，而const版本用于在对象为const时访问栈顶元素。这两个函数通过调用底层容器的back方法实现，该方法返回容器末尾元素的引用。

私有成员变量

Container _c：底层容器实例，用于存储栈中的所有元素。通过选择不同的容器类型（如std::deque、std::vector等），可以改变栈的具体实现细节，如内存分配和元素访问方式。

queue的简单用法

在C++中，队列（Queue）是一种先进先出（First In, First Out，FIFO）的数据结构，它允许在一端（通常是队尾）添加元素，在另一端（队首）移除元素。C++标准库（STL）提供了queue容器适配器，用于实现队列的功能。queue在<queue>头文件中定义。

基本操作

队列主要支持以下几种操作：

push：在队列尾部插入一个元素。

pop：移除队列头部的元素。

front：访问队列头部的元素。

back：访问队列尾部的元素。

empty：检查队列是否为空。

size：返回队列中元素的数量。

使用queue

首先，需要包含queue头文件：

#include <queue>

然后，可以创建和使用queue对象：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // 向队列中添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 显示队列前端和尾端的元素
    std::cout << "Front element: " << q.front() << std::endl;
    std::cout << "Back element: " << q.back() << std::endl;

    // 移除队列前端的元素
    q.pop();

    // 再次显示队列前端的元素
    std::cout << "Front element after pop: " << q.front() << std::endl;

    // 检查队列是否为空
    if (!q.empty()) {
        std::cout << "Queue is not empty." << std::endl;
    }

    // 显示队列的大小
    std::cout << "Queue size: " << q.size() << std::endl;

    return 0;
}

queue的简单实现

/*queue的简单实现*/
#if 1
#include <deque>
#include <vector>
#include<iostream>
using namespace std;

namespace Myqueue
{
    template<class T, class Container = std::deque<T>>
    class queue
    {
    public:
        queue()
        : _c()
        {}
        
         void push(const T& data)
        {
            _c.push_back(data);
        }
        
         void pop()
        {
            if (empty())
            {
                return;
            }
            
             _c.pop_front();
        }
        
         T& front()
        {
            return _c.front();
        }
        
         const T& front()const
        {
            return _c.front();
        }
        
         T& back()
        {
            return _c.back();
        }
        
         const T& back()const
        {
            return _c.back();
        }
        
         size_t size()const
        {
            return _c.size();
        }
        
         bool empty()const
        {
            return _c.empty();
        }
    private:
        Container _c;
    };
    
     
}
#endif

这段代码定义了一个模板类queue，位于Myqueue命名空间中。它是对C++标准库容器的适配，使其表现得像一个队列（Queue）。队列是一种先进先出（First In, First Out，FIFO）的数据结构，这意味着元素从一端添加到队列（队尾），并从另一端（队首）被移除。这个自定义队列通过内部封装了一个容器（默认为std::deque<T>）来实现其功能。

类模板参数

T：队列中存储的元素类型。

Container：底层容器类型，用于实际存储队列中的元素，默认为std::deque<T>。deque（双端队列）是一个允许在两端进行插入和删除操作的序列容器。

成员函数

构造函数 queue()：初始化一个空的队列实例。

push(const T& data)：在队列尾部添加一个元素。这里使用的是底层容器的push_back方法，表示元素总是被添加到容器的尾部。

pop()：移除队列头部的元素。这里使用的是底层容器的pop_front方法，从容器的前端移除元素。如果队列为空（即容器为空），则pop操作不执行任何操作。

front() 和 const T& front()const：返回对队列头部元素的引用。非const版本允许修改队列头部的元素，而const版本用于在对象为const时访问队列头部的元素。这两个函数通过调用底层容器的front方法实现。

back() 和 const T& back()const：返回对队列尾部元素的引用。非const版本允许修改队列尾部的元素，而const版本用于在对象为const时访问队列尾部的元素。这两个函数通过调用底层容器的back方法实现。

size()const：返回队列中元素的数量，即底层容器中元素的数量。

empty()const：检查队列是否为空。如果底层容器为空，这个方法返回true；否则返回false。

私有成员变量

Container _c：底层容器实例，用于存储队列中的所有元素。通过选择不同的容器类型（如std::deque、std::list等），可以改变队列的具体实现细节，如内存分配和元素访问方式。

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 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

用两个队列

class MyStack {
public:
    MyStack() {}

    void push(int x) {
        if (queue1.empty()) {
            queue2.push(x);
        } else {
            queue1.push(x);
        }
    }

    int pop() {
        int ret = 0;
        if (queue1.empty()) {
            while (queue2.size() != 1) {
                queue1.push(queue2.front());
                queue2.pop();
            }
            ret = queue2.front();
            queue2.pop();
            return ret;
        } else {
            while (queue1.size() != 1) {
                queue2.push(queue1.front());
                queue1.pop();
            }
            ret = queue1.front();
            queue1.pop();
            return ret;
        }
    }

    int top() {
        if (queue1.empty()) {
            return queue2.back();
        } else {
            return queue1.back();
        }
    }

    bool empty() { return queue1.empty() && queue2.empty(); }
    queue<int> queue1;
    queue<int> queue2;
};

代码思路

我们只需要保证一个队列为空，一个队列存储栈内元素，对于插入元素直接插入到有元素的栈后面，取元素直接访问队尾的元素即可，抛出元素则需要使得有元素的栈只含有一个元素，其余的复刻到另一个空栈即可，最后把这个只含一个元素的栈清空。

代码解析

成员函数

构造函数 MyStack()：初始化一个空的MyStack对象。这里不需要特别的初始化代码，因为成员队列queue1和queue2在创建时自动初始化为空。

void push(int x)：向栈中添加一个元素。这个操作检查哪个队列不为空，并将新元素添加到那个队列的尾部。如果两个队列都为空，则默认选择queue2作为添加元素的队列。

int pop()：移除栈顶元素并返回它。这个操作涉及到将非空队列中除最后一个元素外的所有元素转移到另一个空队列中，然后返回并移除那个最后的元素，从而实现了栈的LIFO行为。

int top()：返回栈顶元素，但不移除它。这通过返回当前非空队列的尾部元素来实现，因为在push操作中，新加入的元素总是位于非空队列的尾部。

bool empty()：检查栈是否为空。这通过检查两个队列是否都为空来实现。

工作原理

Push 操作：选择非空队列将新元素加入其尾部。如果两个队列都为空，选择一个队列（如queue2）加入新元素。这样做保证了所有已有的元素都在一个队列中，而新元素被添加到了这个队列的尾部。

Pop 操作：将非空队列中的所有元素，除了最后一个元素，转移到另一个队列中。最后一个元素正是最后被加入的元素，符合栈的后进先出特性。然后返回并移除这个最后的元素。

Top 操作：直接返回非空队列的尾部元素。由于新加入的元素总是在非空队列的尾部，因此这个元素就是栈顶元素。

Empty 操作：当两个队列都为空时，栈为空。

示例

假设进行以下操作序列：push(1), push(2), top(), pop(), empty()。

push(1)：queue2接收元素1（因为两个队列都为空）。

push(2)：由于queue2不为空，元素2也被加入queue2。

top()：返回queue2的尾部元素，即2。

pop()：将queue2中的所有元素（这里是1和2），除了最后一个元素外，转移到queue1。然后返回并移除queue2中最后一个元素（2）。现在queue1包含元素1，queue2为空。

empty()：检查两个队列是否都为空。根据上述操作，queue1不为空，所以返回false。

用一个队列

class MyStack {
public:
    queue<int> q;

    /** Initialize your data structure here. */
    MyStack() {}

    /** Push element x onto stack. */
    void push(int x) {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int r = q.front();
        q.pop();
        return r;
    }

    /** Get the top element. */
    int top() {
        int r = q.front();
        return r;
    }

    /** Returns whether the stack is empty. */
    bool empty() { return q.empty(); }
};

代码思路