Read this in other languages: English, Português
- What is a stack?
- Where are stacks used?
- How to implement a stack?
- What are the basic operations in stacks?
A stack is a linear data structure in which elements are added and removed from the same end. Because of this characteristic, stacks are also known as LIFO (Last-In First-Out) structures.
An analogy for this data structure is a stack of books. Books are always placed and removed from the top of the stack.
- Undo and Redo -- Stacks are used in text editors to store user actions, allowing for undoing and redoing actions.
- Navigation History -- Stacks are used to store the pages visited by the user in a web browser, allowing the user to go back to the previous page when the "back" button is pressed.
- Search Algorithms -- Stacks are used in search algorithms to store pending states to be explored.
- Execution Stacks -- When a function is called, the parameters and the return address are pushed onto the stack. When the function returns, the return address is popped and control is transferred back to the previous call.
A stack s can be constructed with the following components:
s.cells[]: cells that store the elements of the stack.s.top: a pointer that references the top element of the stack.s.size: an integer that counts the number of elements in the stack.
size()returns the number of elements in a stack.push()inserts an element on top of a stack.pop()removes the top element of a stack.
- Return the value of
p.size.
- Update the top pointer of stack
s.topto reference a new cell. - Store the element
xin the cell referenced by the top pointer of stacks.top. - Increment the size counter of stack
s.sizeby one.
- Check if stack
sis empty. If yes, go to Step 2. Otherwise, go to Step 3. - The stack is empty, so return
"empty stack". - Save in x the element referenced by the top pointer of stack
s.top. - Update the top pointer of stack
s.topto reference the cell below the current top. - Decrement the size counter of stack
s.sizeby one. - Return element
x.