[C++] stack, queue and deque

Introduction to stack

  1. Stack is a container adapter that is specially used in contexts with last-in-first-out operations. Its deletion can only insert and extract elements from one end of the container.
  2. Stack is implemented as a container adapter. A container adapter encapsulates a specific class as its underlying container and provides a set of specific member functions to access its elements. It uses a specific class as its underlying, element-specific container at the end ( That is, the top of the stack) is pushed and popped.
  3. The underlying container of the stack 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 the tail element operation
    • push_back: tail insertion element operation
    • pop_back: tail deletion element operation
  4. The standard containers vector, deque, and list all meet these requirements. By default, if no specific underlying container is specified for the stack, deque is used by default.

Introduction to queue

  1. A queue is a container adapter designed to operate in a FIFO context (first in, first out), where elements are inserted from one end of the container and extracted from the other end.
  2. The queue is implemented as a container adapter. The container adapter encapsulates a specific container class as its underlying container class. Queue provides a specific set of member functions to access its elements. Elements are put into the queue from the end of the queue and dequeued from the head.
  3. The underlying container can be one of the standard container class templates or other specially designed container classes. The underlying container should support at least the following operations:
    • empty: Check whether the queue is empty
    • size: Returns the number of valid elements in the queue
    • front: Returns a reference to the head element of the team
    • back: Returns a reference to the last element of the queue
    • push: queue at the end of the queue
    • pop: dequeue at the head of the queue
  4. The standard container classes deque and list meet these requirements. By default, if no container class is specified for queue instantiation, the standard container deque is used.

Common interface descriptions and simple demonstrations of stack and queue



We can see that there are no iterators in the stack and queue. This is because the characteristics of the stack and queue are first-in-last-out and last-in-first-out. We do not need to traverse the stack and queue. If we can traverse the stack and queue, problems will arise. Its characteristics will be changed.

void test_stack() //FILO -- first in last out
{<!-- -->
std::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{<!-- -->
std::cout << st.top() << " ";
st.pop();
}
std::cout << std::endl;
}

void test_queue() //FIFO -- frist in frist out
{<!-- -->
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{<!-- -->
std::cout << q.front() << " ";
q.pop();
}
std::cout << std::endl;
}

Simulation implementation of stack and queue

template<class T,class Container = std::deque<T>>
class stack
{<!-- -->
public:
void push(const T & x)
{<!-- -->
_con.push_back(x);
}
void pop()
{<!-- -->
_con.pop_back();
}
size_t size()
{<!-- -->
return _con.size();
}
T & top()
{<!-- -->
return _con.back();
}
bool empty()
{<!-- -->
return _con.empty();
}
private:
Container_con;
};

template<class T, class Container = std::deque<T>>
class queue
{<!-- -->
public:
void push(const T & x)
{<!-- -->
_con.push_back(x);
}
void pop()
{<!-- -->
_con.erase(_con.begin());
}
T & front()
{<!-- -->
return _con.front();
}
T & back()
{<!-- -->
return _con.back();
}
size_t size()
{<!-- -->
return _con.size();
}
bool empty()
{<!-- -->
return _con.empty();
}
private:
Container_con;
};

Container adapter: deque


Advantages of deque:

  • Insert and delete at any position
  • Support random access

It can be said to be a combination of list and vector, but it also has disadvantages. Let’s take a look at it together:

deque (double-ended queue): It is a double-opening “continuous” space data structure. The meaning of double-opening is that insertion and deletion operations can be performed at both ends, and the time complexity is O(1), which is the same as Compared with vector, header insertion is more efficient and does not require moving elements; compared with list, space utilization is relatively high.
In fact, deque is not a truly continuous space, but is made up of continuous small spaces. The actual deque is similar to a dynamic two-dimensional array, and its underlying structure is as shown in the figure below:

The essence is to open multiple small array buffers. The first small array buffer is used for head insertion, and the last small array buffer is used for tail insertion. The middle array is used to store intermediate data. As long as one small array is full, another small array will be opened. , the sizes of the small arrays are all the same, and they all store n data. There is also a central control array, which is an array of pointers, with each element pointing to the address of the first element of each small array.

The bottom layer of the double-ended queue is an imaginary continuous space, which is actually segmented. In order to maintain its “overall continuity” and the illusion of random access, it falls on the iterator of deque, so the iterator design of deque is more complicated. As shown below:

  • cur points to the current data location
  • first and last represent the beginning and end of the current buffer Finish
  • node points to the current location in the central control array The node pointer of the buffer.

For the current buffer, just let cur keep + +. Wait until cur reaches last and then + +. The node will point to the node pointer of the next buffer, and then let first and last be updated to the head and tail of the next buffer. , and then let cur point to first to complete the random access to the data.

Disadvantages of deque:

  • Compared with vector, the advantages of deque are: header insertion and deletion When expanding, there is no need to move elements, so the efficiency is very high. Moreover, when expanding, there is no need to move a large number of elements, so its efficiency must be high.
  • Compared with list, the bottom layer is a continuous space. The space utilization is relatively high and there is no need to store additional fields.
  • However, deque has a fatal flaw: it is not suitable Traversal, because when traversing, the iterator of deque needs to frequently detect whether it moves to the boundary of a certain small space, resulting in low efficiency. In sequential scenarios, frequent traversal may be required, so in practice, a linear structure is required In most cases, vector and list are given priority. There are not many applications of deque. One application that can be seen so far is that STL uses it as the underlying data structure of stack and queue.

Stack is a special linear data structure with last-in-first-out function. Therefore, any linear structure with push_back() and pop_back() operations can be used as the underlying container of stack, such as vector and list; queue is a special first-in-first-out function. Linear data structures, as long as they have push_back and pop_front operations, can be used as the underlying container of queue, such as list. However, deque is selected as the underlying container by default for stack and queue in STL, mainly because:

  • stack and queue do not need to be traversed (therefore stack and queue do not have iterators ), only need to operate on one or both fixed ends.
  • When the elements in the stack grow, deque is better than vector High efficiency (no need to move a large amount of data when expanding); when the elements in the queue grow, deque is not only efficient, but also has high memory usage.

This combines the advantages of deque and perfectly avoids its shortcomings.