Introduction
A stack is a commonly used linear data structure in OI. Note that this article mainly discusses the stack data structure, rather than the system stack/stack space used at runtime.
The modification and access of a stack follow the last-in-first-out principle, so a stack is often called a last-in-first-out (last in first out) list, abbreviated as a LIFO list.
Warning
LIFO means that the item that entered last among those currently in the container leaves first.
Consider the following stack:
push(1)
pop(1)
push(2)
pop(2)
If we consider the whole sequence, 1 is pushed first and popped first, while 2 is pushed last and popped last, so this becomes a first-in-first-out list, which is obviously wrong.
Therefore, when deciding whether a data structure is LIFO or FIFO, consider what is currently inside the container.
Using an Array to Simulate a Stack
We can easily use an array to simulate a stack, as follows:
Implementation
C++
int st[N];
// Here, st[0] (that is, *st) stores the number of elements in the stack and is also the index of the top
// Push:
st[++*st] = var1;
// Read the top:
int u = st[*st];
// Pop: note the out-of-bounds issue; when *st == 0, nothing more can be popped
if (*st) --*st;
// Clear the stack
*st = 0;
Python
st = [0] * N
# Here, st[0] stores the number of elements in the stack and is also the index of the top
# Push:
st[st[0] + 1] = var1
st[0] = st[0] + 1
# Read the top:
u = st[st[0]]
# Pop: note the out-of-bounds issue; when *st == 0, nothing more can be popped
if st[0]:
st[0] = st[0] - 1
# Clear the stack
st[0] = 0
Stack in the C++ STL
C++'s STL also provides a std::stack container; before using it, include the stack header file.
Definition of stack in the STL
// clang-format off
template<
class T,
class Container = std::deque<T>
> class stack;
T is the data type to be stored in the stack.
Container is the underlying container type used to store the elements. This container must provide the following functions with their usual semantics:
back()push_back()pop_back()
The STL containers std::vector, std::deque, and std::list satisfy these requirements. If none is specified, std::deque is used as the underlying container by default.
The STL stack container provides a set of member functions for calling, among which the commonly used ones are:
- Element access
st.top()returns the top element
- Modification
st.push()inserts the passed argument at the topst.pop()pops the top element
- Capacity
st.empty()returns whether it is emptyst.size()returns the number of elements
In addition, std::stack provides some operators. The most commonly used is the assignment operator = to assign to a stack, as in the following example:
// Create two stacks, st1 and st2
std::stack<int> st1, st2;
// Load 1 into st1
st1.push(1);
// Assign st1 to st2
st2 = st1;
// Output the top element of st2
cout << st2.top() << endl;
// Output: 1
Simulating a Stack with a Python list
In Python, you can use a list to simulate a stack:
Implementation
st = [5, 1, 4]
# Use append() to add elements to the top of the stack
st.append(2)
st.append(3)
# >>> st
# [5, 1, 4, 2, 3]
# Use pop to take the top element
st.pop()
# >>> st
# [5, 1, 4, 2]
# Use clear to empty the stack
st.clear()