Explore the English language on a new scale using AI-powered English language navigator.

Stack

Stack is one of the fundamental data structures in computer science and it is used in many algorithms and applications. As an example, stack is used:

implicitly in recursion;
for expression evaluation;
to check the correctness of parentheses sequence;
etc.

First of all, we will describe Stack ADT and then show two different implementations.

Stack ADT

Well illustration from the real world is a stack of books, where you can operate with a "top" of the stack only. We will dedicate six operations on the stack. You can put a book on top (push); look, which one lays on top of a stack (peek) and remove a topmost book (pop) and check, if stack is empty (isEmpty). Also, there are two operations to create and to destroy a stack. Let us structure them up in the following list.

Operations

Stack create()
creates empty stack
boolean isEmpty(Stack s)
tells whether the stack s is empty
push(Stack s, Item e)
put e on top of the stack s
Item peek(Stack s)
returns topmost element in stack s
Precondition: s is not empty
pop(Stack s)
removes topmost element from the stack s
Precondition: s is not empty
destroy(Stack s)
destroys stack s

Note. In different sources peek operation may be called top.

Axioms

newly created stack is empty;
after pushing an item to a newly created stack, it becomes nonempty;
peek returns the most recently pushed item;
stack remains untouched, after a pair of push and pop commands, executed one after another.

It is a formal definition. Let us step forward to more intuitive examples, before we turn to implementation issues.

Example

Sketchy, stack can be shown like this:

Singly-linked list example

Implementations

We are going to discuss two implementations of the Stack ADT. Each of them has it's own advantages and disadvantages, which are examined in the articles below: