Stack

Stack is a linear data structure commonly used in OI. Please note that this article mainly talks about the data structure of the stack, not the system stack/stack space when the program is running.

The stack is modified and accessed according to the last-in-first-out principle, so the stack is often called a last-in-first-out (last in first out) table, or LIFO table for short.

Implementation Using Array

C++

int st[N];

// st[0] (i.e. *st) is used here to represent the number of elements in the stack and is also the subscript on the top of the stack

// Push on the stack:

st[++*st] = var1;

// Get the top of the stack:

int u = st[*st];

// Pop the stack: Pay attention to the out-of-bounds problem, when *st == 0, you cannot continue to pop.

if (*st) --*st;

// Clear the stack

*st = 0;

Python

st = [0] * N

# st[0] is used here to represent the number of elements in the stack, and is also the subscript of the top of the stack

# Push on the stack:

st[st[0] + 1] = var1

st[0] = st[0] + 1

# Get the top of the stack:

u = st[st[0]]

# Pop stack: pay attention to out-of-bounds issues, when *st == 0, popping cannot continue

if st[0]:

     st[0] = st[0] - 1

# Clear the stack

st[0] = 0

STL in C++ also provides a container std::stack, which needs to introduce the stack header file before use.

C++ STL

STL in C++ also provides a container std::stack, which needs to introduce the stack header file before use.

ⓘ Definition of stack in 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 elements. The container must provide the following functions with the usual semantics:

back()

push_back()

pop_back()

The STL containers std::vector, std::deque, and std::list satisfy these requirements. If not specified, std::deque is used as the underlying container by default.

The stack container in STL provides a number of member functions for calling, among which the more commonly used ones are:

st.top() returns to the top of the stack

st.push() inserts the passed parameters to the top of the stack

st.pop() pops the top of the stack

st.empty() returns whether it is empty

st.size() returns the number of elements

In addition, std::stack also provides some operators. The more commonly used one is to use the assignment operator = to assign a value to the stack. Example: The stack container in STL provides a number of member functions for calling, among which the more commonly used ones are:

// Create two new stacks st1 and st2

std::stack<int> st1, st2;


// Load st1 with 1

st1.push(1);


// Assign st1 to st2

st2 = st1;


// Output the top element of st2

cout << st2.top() << endl;


// Output: 1

Simulating Stack in Python

In Python, you can use lists to simulate a stack:

st = [5, 1, 4]

# Use sppend() to put element into the stack

st.append(2)

st.append(3)

# >>> st

# [5, 1, 4, 2, 3]

# Use pop to take the top element in the stack

st.pop()

# >>> st

# [5, 1, 4, 2]

# Use clear to clear the stack

st.clear()