Tech

Stack

No Comments

Definition

Stack is a dynamic set of elements. Stack is an elementary data structure, however it is a very useful and monumental construction. The fact that Java-Virtual Machine is a stack-based machine prove to us that stack is a really important structure.

Stack stores elements in a certain way. Each element can be added to the top and deleted from the top. The element which is going to be deleted from the stack is the one most recently inserted. The removed operation is predefined. The stack implements LIFO policy. LIFO means a last-in, first-out.

Stack methods are:

PUSH(ELEMENT) - the insert operation
POP() - the delete operation
PEEK() - the top element
SIZE() - how many elements are in the stack
ISEMPTY() - indicate if stack has no elements

How it works

  • Imagine an empty Stack:

  • Let`s push several elements to our stack:


PUSH(7)
PUSH(9)
PUSH(1)
PUSH(5)

First element was equal 7 and it was put under the first index of the stack structure. In other words it was put on the first place in the stack.
Element 9 was added as the second element and it was stored under index equals 2.
The last added element was 5 under index 4 and it is the top of the stack until we add some new element.

  • Let`s call  PEEK(), SIZE() and ISEMPTY() methods:

PEEK() returns 5, because 5 was added the last one;
SIZE()  returns 4, because we added 4 elements into the stack;
ISEMPTY() returns false, because our stack is not empty;

  • Let`s delete two elements by executing POP() method twice in sequence:

POP() returns 5 and removes this element from the stack;
POP() returns 1 and removes this element from the stack;

  • Let`s again call  PEEK(), SIZE() and ISEMPTY() methods:

PEEK() returns 9, because two other elements were deleted and ít became the first element on the top of the stack;
SIZE()  returns 2, because two elements was remained within the stack;
ISEMPTY() returns false, because the stack is not empty;

  • Let`s execute POP() method three times in sequence:
  1. POP() returns 9, because it is on the top of the stack and removes the element from the stack;
  2. POP() returns 7 and removes the element from the stack;
  3. POP() returns ERROR. Why?  Every time when POP() method is called it is necessary to check whether the stack is empty or not. When the stack contains no elements but we attempt to pop an element from it, such situations are called  “the stack underflows” and it is needed to throw an error message.


Examples on GitHub:

Code example for the above article: https://github.com/materiaBio/DataStructures/tree/master/src/stack/pseudocode

URL on GitHub to DataStructures project: https://github.com/materiaBio/DataStructures

You may also like