c++之 stack(栈)和queue(队列)

 

目录

stack(栈)

相关介绍和使用

 接口的使用：

容器适配器

stack模拟实现

queue(队列)

相关介绍和使用

 函数声明 接口说明

queue模拟实现

---

stack(栈)

相关介绍和使用

文档：stack - C++ Reference

1.  stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行 元素的插入与提取操作。
2.  stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。
4.  stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作：

• empty：判空操作 back：取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

 他和我们的数据结构中的栈是一样的功能，就是我们的库里面帮助我们实现了并且提供了相关的接口。

 接口的使用：

1.   empty：判断栈是否为空

这个是用来判断我们的栈是否为空，返回一个布尔值。

// stack::empty
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;
  int sum (0);

  for (int i=1;i<=10;i++) mystack.push(i);

  while (!mystack.empty())
  {
     sum += mystack.top();
     mystack.pop();
  }

  std::cout << "total: " << sum << '\n';

  return 0;
}

2.  size：求栈的元素个数

他是用来求我们的栈里面的元素的个数

// stack::size
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> myints;
  std::cout << "0. size: " << myints.size() << '\n';

  for (int i=0; i<5; i++) myints.push(i);
  std::cout << "1. size: " << myints.size() << '\n';

  myints.pop();
  std::cout << "2. size: " << myints.size() << '\n';

  return 0;
}

3.  top：返回我们栈顶的元素

 

 返回我们栈顶元素

// stack::top
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  mystack.push(10);
  mystack.push(20);

  mystack.top() -= 5;

  std::cout << "mystack.top() is now " << mystack.top() << '\n';

  return 0;
}

4.  push：将我们的元素入栈

 

 将我们的元素入栈

// stack::push/pop
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  for (int i=0; i<5; ++i) mystack.push(i);

  std::cout << "Popping out elements...";
  while (!mystack.empty())
  {
     std::cout << ' ' << mystack.top();
     mystack.pop();
  }
  std::cout << '\n';

  return 0;
}

5.   pop：将我们的元素出栈

将我们的元素出栈

// stack::push/pop
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  for (int i=0; i<5; ++i) mystack.push(i);

  std::cout << "Popping out elements...";
  while (!mystack.empty())
  {
     std::cout << ' ' << mystack.top();
     mystack.pop();
  }
  std::cout << '\n';

  return 0;
}

 从栈的接口中可以看出，栈实际是一种特殊的vector，因此我们的栈的底层可以用一个vector去实现，但是如果我们的地层层直接用一个vector 的话就将我们的额栈写死了，因为我们还有可能是链栈等。

 所以我们的可以先来了解一下我们的容器适配器。

容器适配器

什么是容器适配器：  适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

容器适配器和我们的电流适配器一样：

       我们的平时的电压是220v，然而这个如果直接和我们的那先家具什么的直接连接的话，我们的东西很可能会报废，因为所需要的电压不同，他承受不了，也会有很大的安全隐患，所以就需要我们的电流适配器，将我们的220v电压转换成我们所需要的电压。

适配器的模式可以认为是将一种接口转化成为我们所需要的接口

我们库里面的栈的也是我们的容器适配器。利用模板，stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。

 

 我们栈的实现就可以传一个参数来进行，这样就可以实现，当你需要vector的栈时，传vector等。

stack模拟实现

因为我们的stack就是对其它接口进行了包装，所以我们的在模拟实现的时候就只需要我们的调用它的相关接口。所以我们的这里的实现是非常简单的。

需要注意的一点是我们的栈并没有实现随机访问这个点。也就是operator[]的重载。

利用多一个模板参数来进行实现我们的底层不同形式的栈。

template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		const T& top() const
		{
			
			return _con.back();
		}

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

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

	private:
		Container _con;
	};

queue(队列)

相关介绍和使用

文档：queue - C++ Reference

1.  队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标 准容器deque。 
4. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作：

•  empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

 

 函数声明 接口说明

queue() 构造空的队列和构造函数

// constructing queues
#include <iostream>       // std::cout
#include <deque>          // std::deque
#include <list>           // std::list
#include <queue>          // std::queue

int main ()
{
  std::deque<int> mydeck (3,100);        // deque with 3 elements
  std::list<int> mylist (2,200);         // list with 2 elements

  std::queue<int> first;                 // empty queue
  std::queue<int> second (mydeck);       // queue initialized to copy of deque

  std::queue<int,std::list<int> > third; // empty queue with list as underlying container
  std::queue<int,std::list<int> > fourth (mylist);

  std::cout << "size of first: " << first.size() << '\n';
  std::cout << "size of second: " << second.size() << '\n';
  std::cout << "size of third: " << third.size() << '\n';
  std::cout << "size of fourth: " << fourth.size() << '\n';

  return 0;
}

empty() 检测队列是否为空，是返回true，否则返回false

 

判空： 

// queue::empty
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myqueue;
  int sum (0);

  for (int i=1;i<=10;i++) myqueue.push(i);

  while (!myqueue.empty())
  {
     sum += myqueue.front();
     myqueue.pop();
  }

  std::cout << "total: " << sum << '\n';

  return 0;
}

size() 返回队列中有效元素的个数

 

返回元素个数 

#include <iostream>       // std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myints;
  std::cout << "0. size: " << myints.size() << '\n';

  for (int i=0; i<5; i++) myints.push(i);
  std::cout << "1. size: " << myints.size() << '\n';

  myints.pop();
  std::cout << "2. size: " << myints.size() << '\n';

  return 0;
}

front() 返回队头元素的引用

#include <iostream>       // std::cout
#include <queue>          // std::queue

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

  myqueue.push(77);
  myqueue.push(16);

  myqueue.front() -= myqueue.back();    // 77-16=61

  std::cout << "myqueue.front() is now " << myqueue.front() << '\n';

  return 0;
}

back() 返回队尾元素的引用

 

// queue::back
#include <iostream>       // std::cout
#include <queue>          // std::queue

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

  myqueue.push(12);
  myqueue.push(75);   // this is now the back

  myqueue.back() -= myqueue.front();

  std::cout << "myqueue.back() is now " << myqueue.back() << '\n';

  return 0;
}

push() 在队尾将元素val入队列

// queue::push/pop
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while (!myqueue.empty())
  {
    std::cout << ' ' << myqueue.front();
    myqueue.pop();
  }
  std::cout << '\n';

  return 0;
}

pop() 将队头元素出队列

 

// queue::push/pop
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while (!myqueue.empty())
  {
    std::cout << ' ' << myqueue.front();
    myqueue.pop();
  }
  std::cout << '\n';

  return 0;
}

 我们的队列和我们的栈是一样的，都是属于我们的额容器适配器，因为他的底层也是对我们的其他的容器进行封装。

所以实现和我们的stack是一样的

queue模拟实现

通过多传入一个模板参数，来将我们的底层的具体实现改变。 

template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_front();
		}

		const T& front() const
		{
			return _con.front();
		}

		const T& back() const
		{
			return _con.back();
		}

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

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

	private:
		Container _con;
	};

头文件问题：

当我们实现完我们的栈和队列之后，我们去使用，再包含我们的头文件是可能会有相关头文件找不到的报错。

 

 

 因为在我们的再找相关声明的时候默认不会在我们的库里面去寻找，没有进行展开的话。

我们自己的头文件应该放在我们的库里面的头文件的后面 ，因为我们再找相关的头文件只会在向上寻找，并不会向下寻找，若是找不到相关的声明，就会报错。