1. In the STL, **stack and queue** differ from containers like string, vector, and list as they are **container adapters**;
2. Container adapters fundamentally reuse existing storage structures rather than implementing their own. They provide specific interfaces based on requirements. Reverse iterators are adapted from forward iterators;
n3. The adapter pattern is a well-established design pattern;
4. Stack and queue lack iterator support, preventing arbitrary traversal;
5. Reverse Polish notation (postfix expressions). Regular arithmetic expressions use infix notation, which computers struggle to parse for operator precedence. Computers convert infix expressions to postfix expressions where operands maintain their order while operators are arranged by precedence;
6. Compilers only perform upward searches, not downward ones, to optimize compilation speed;
Basic Usage of Stack and Queue
template > class stack;
template > class queue;
Other containers use allocators as their second template parameter, while container adapters utilize other containers for storage;
Stack Implementation
stack st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.size() << endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
Queue Implementation
queue q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
cout << q.size() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
Custom Stack and Queue Implementations
1. To support container adapters, both vector and list provide front() and back() interfaces;
2. Template parameters support default values;
3. Using vector for queue implementation requires data shifting, which is inefficient. The standard library doesn't support vector adaptation for queues due to this limitation, instead using pop_front();
Stack Implementation
namespace Stack
{
template >
class stack
{
public:
void push(const T &val)
{
con_.push_back(val);
}
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 Implementation
namespace Queue
{
template >
class queue
{
public:
void push(const T &val)
{
con_.push_back(val);
}
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_;
};
}
Deque (Double-Ended Queue)
1. Deque is not a queue but a container that supports insertion and deletion at both ends;
2. Deque iterators are random access iterators;
3. Deque lacks reserve() functionality. While it has expansion logic, it cannot allocate all required space at once;
Deque Interface
Element access:
operator[]
at
front
back
Modifiers:
assign
push_back
push_front
pop_back
pop_front
insert
erase
swap
clear
emplace
emplace_front
emplace_back
Comparison of Vector and List
Vector: Advantages: 1. Supports random access via subscript; 2. CPU loads contiguous blocks, enabling high-speed cache utilization; Disadvantages: 1. Expansion issues - requires reallocation and data copying; 2. Inefficient insertion/deletion at the middle or beginning;
List: Advantages: 1. Efficient insertion/deletion at any position with on-demand allocation; Disadvantages: 1. No subscript access support;
Deque Implementation
Deque allocates n contiguous blocks of fixed size, plus a central control array (pointer array). The central array starts from its middle, storing addresses of these n blocks. When the central array needs expansion, the cost is minimal compared to vector expansion - only pointer variables need copying.
The first buffer array is filled from back to front.
Iterator design is complex: first points to the buffer's start, last to its end, cur to the current position, and node is a secondary pointer to the central array for accessing other buffers. The start iterator points to the first buffer, finish to the last buffer. *it and != comparison use cur, while ++ operation utilizes four pointers.
Characteristics
Compared to vector: Significantly addresses expansion and head insertion/deletion issues, but [] implementation is complex. It requires calculating which buffer contains the element and then the specific position within that buffer. For example: 1. First check if it's in the first buffer - if so, access by position; 2. If not in the first buffer, subtract the first buffer's size, then divide and modulo by each buffer's maximum size to find the correct buffer and position before accessing.
Compared to list: Supports subscript access with high CPU cache efficiency, but middle insertion efficiency is poor. Options include: 1. Data shifting, which is costly; 2. Buffer expansion, which would further degrade [] efficiency since buffer sizes would no longer be fixed. The standard library doesn't implement this approach;
Deque Usage Scenarios
1. Default container for adapting stack and queue;
Deque offers efficient head/tail insertion and deletion operations. Vector has expansion and head operation inefficiencies, while list suffers from poor cache utilization due to individual memory allocations.