Skip to content

Stack

Introduction

A stack is a commonly used linear data structure in OI. Please note that this article primarily discusses the stack data structure, not the system stack/stack space during program execution.

Modifications and access to a stack follow the Last-In-First-Out principle, hence a stack is often referred to as a Last-In-First-Out (LIFO) list.

Warning

LIFO describes that the currently last element in the container is the first to be removed.

Consider the following stack operations:

1
2
3
4
push(1)
pop(1)
push(2)
pop(2)

If considered as a whole, 1 is pushed first and popped first, 2 is pushed last and popped last, which would make it a First-In-First-Out list—clearly incorrect.

Therefore, when determining whether a data structure is LIFO or FIFO, one should consider the state within the current container.

Simulating a Stack Using an Array

We can conveniently simulate a stack using an array, as shown below:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int st[N];
// Here, st[0] (i.e., *st) represents the number of elements in the stack and also the top index

// Push:
st[++*st] = var1;
// Get top:
int u = st[*st];
// Pop: Note the out-of-bounds issue; cannot pop when *st == 0
if (*st) --*st;
// Clear stack:
*st = 0;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
st = [0] * N
# Here, st[0] represents the number of elements in the stack and also the top index

# Push:
st[st[0] + 1] = var1
st[0] = st[0] + 1
# Get top:
u = st[st[0]]
# Pop: Note the out-of-bounds issue; cannot pop when st[0] == 0
if st[0]:
    st[0] = st[0] - 1
# Clear stack:
st[0] = 0

Stack in C++ STL

The C++ STL also provides a container std::stack. Include the <stack> header to use it.

STL Definition of stack 
1
2
3
4
5
// 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. This container must provide the following functions with their usual semantics:

  • back()
  • push_back()
  • pop_back()

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

The stack container in STL provides a set of member functions for use. The more commonly used ones are:

  • Element Access
    • st.top() returns the top element of the stack.
  • Modifiers
    • st.push() inserts the passed argument onto the top of the stack.
    • st.pop() removes the top element from the stack.
  • Capacity
    • st.empty() returns whether the stack is empty.
    • st.size() returns the number of elements.

Additionally, std::stack provides some operators. The most commonly used is the assignment operator = to assign one stack to another. Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Create two stacks st1 and st2
std::stack<int> st1, st2;

// Push 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 Using Python's List

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

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
st = [5, 1, 4]

# Use append() to add an element to the top
st.append(2)
st.append(3)
# >>> st
# [5, 1, 4, 2, 3]

# Use pop to remove the top element
st.pop()
# >>> st
# [5, 1, 4, 2]

# Use clear to empty the stack
st.clear()

References

  1. std::stack - zh.cppreference.com
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用