Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

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:

Visualizers

  1. Stack in Java Applets Centre

Recommended books

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
  3. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  4. Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Partners Ads                

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: