[hand torn STL] Stack & queue

stack Introduction and use of

1. stack Is a container adapter , Specifically used in context with LIFO operations , The deletion can only be performed by inserting and extracting elements from one end of the container .
2. stack Is implemented as a container adapter , A container adapter is a container that encapsulates a specific class as its underlying container , And provide a specific set of member functions to access its elements , Use a specific class as its underlying , The tail of an element specific container ( The top of the stack ) Pressed and ejected .
3. stack The underlying container can be any standard container class template or some other specific container class , These container classes should support the following operations ：

• empty： Empty operation
• back： Get tail element operation
• push_back： Tail insert element operation
• pop_back： Tail delete element operation

4. Standard containers vector、deque、list All meet these needs , By default , If not for stack Specify a specific underlying container , By default deque.

notes ：stack and queue It's the adapter （ adapter ）, Is implemented by transformation , It is not implemented directly , It is implemented by encapsulating other container packaging transformations

stack Use

void test_stack()
{
    
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	cout << st.size() << endl;
	while (!st.empty())
	{
    
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
	cout << st.size() << endl;
}

stack Simulation Implementation of

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<deque>
#include<vector>
#include<list>
using namespace std;

namespace lc
{
    
	template<class T,class Container=deque<T>>
	//stack It's a container adapter （ Encapsulation conversion ） Coming out 
	class stack
	{
    
	public:
		void push(const T& x)
		{
    
			_con.push_back(x);
		}
		void pop()
		{
    
			_con.pop_back();
		}
		const T& top()
		{
    
			return _con.back();
		}
		size_t size()
		{
    
			return _con.size();
		}
		bool empty()
		{
    
			return _con.empty();
		}
	private:
		Container _con;
	};
	
}

queue Introduction and use of

1. A queue is a container adapter , Used exclusively in FIFO Context ( fifo ) In the operation , Where the element is inserted from one end of the container , Extract the element at the other end .
2. Queues are implemented as container adapters , The container adapter encapsulates a specific container class as its underlying container class ,queue Provide a specific set of member functions to access its elements . Elements are queued from the end of the queue , Get out of the queue from the head of the queue .
3. The underlying container can be one of the standard container class templates , It can also be other specially designed container classes . The bottom container shall support at least the following operations :

• empty： Check if the queue is empty
• size： Returns the number of valid elements in the queue
• front： Returns a reference to the queue header element
• back： Returns a reference to the end of the queue element
• push_back： Enter the queue at the end of the queue
• pop_front： Get out of the queue at the head of the queue

4. Standard container class deque and list Meet these requirements . By default , If not for queue Instantiate the specified container class , Use standard containers deque.

queue Use

void test_queue()
{
    
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	cout << q.size() << endl;
	while (!q.empty())
	{
    
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
	cout << q.size() << endl;
}

queue Simulation Implementation of

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<deque>
#include<vector>
#include<list>
using namespace std;

namespace lc
{
    
	template<class T, class Container = deque<T>>
	//queue It's a container adapter （ Encapsulation conversion ） Coming out 
	class queue
	{
    
	public:
		void push(const T& x)
		{
    
			_con.push_back(x);
		}
		void pop()
		{
    
			_con.pop_front();
		}
		const T& front()
		{
    
			return _con.front();
		}
		const T& back()
		{
    
			return _con.back();
		}
		size_t size()
		{
    
			return _con.size();
		}
		bool empty()
		{
    
			return _con.empty();
		}
	private:
		Container _con;
	};
	
}

Container adapter

An adapter is a design pattern ( Design patterns are a set of things that are used repeatedly 、 Most people know that 、 Catalogued 、 Summary of code design experience ), This pattern is to convert the interface of one class into another interface that the customer wants .

notes ： although stack and queue You can also store elements in , But in STL It is not divided into the ranks of containers in , Instead, call it a container adapter , This is because stack And queues just wrap the interfaces of other containers ,STL in stack and queue By default deque

Add ：
vector（ Continuous physical space ）：
advantage ：

• Random access
• CPU High cache hit rate

shortcoming ：

• Space is not enough , Need to increase capacity , Increasing capacity costs a lot , There is also a certain waste of space
• Head and middle insert delete , Low efficiency O(N)

list：
advantage ：

• Apply for space on demand to free up space
• Inserting and deleting data anywhere is O(1) Efficient

shortcoming ：

• Random access is not supported
• CPU Low cache hit rate

deque Advantages and disadvantages ：

• deque , Description is very suitable for head plug removal , Tail insertion and tail deletion , To do stack and queue The default adapter container for
• Insert and delete data in the middle of the double ended queue , It's troublesome and inefficient （1. Move the overall data 、2. Move current buff data – Record each buff Size of array , Every buff The array size is inconsistent ）
• deque It's a compromise design , Not extreme enough , Random access is less efficient than vector, Insert delete at any position list
• A pile of data needs to be sorted vector、 Insert and delete at any position list、 Head and tail insert delete multi-purpose deque

notes ： combination list and vector Advantages and disadvantages , Can improve the design Central control array （ Pointer array ）、 Fixed length buff Array data structure deque