Stack Data Structure

  1. Stack Data Structure
  2. Queue Data Structure
  3. Questions on Stack And Queue

What is Stack?

Think Stack as naturally model piles of objects, for example the dinner plates. After a new plate is washed, it is pushed on the top of the stack. When serving food, a clean plate is popped off the stack. Here the plates don’t care which one to be used next that is one of most important reason to use Stack data structure.

Important points:

  • Stack is a container where items are retrieved by last-in, first-out (LIFO) order.
  • Stack is the right container to use when retrieval order doesn’t matter
  • Stack order is important in processing any properly nested structure. This includes recursive calls, parenthesized formula such as postfix evaluation, and depth first search traversal in Graph etc.
  • Stacks are very simple to implement.

Operations on a Stack:

  • push(x): Insert item x at the top of stack.
  • pop(): Return and remove the top element of stack.
  • peek(): Return the top element of stack.
  • full(): Test whether the more items can be pushed to the stack.
  • empty(): Test whether the more items can be popped from the stack.

Implementation of Stack Data Structure:

  1. Implement using simple array. (bounded)
  2. Implement using linked list. (unbounded)

Stack using array: This is very easy to implement. Create an array to hold the Stack values. Maintain a top which will point to the currently pushed element. Initially the top will be -1.
When you push a value to the Stack, you increment the top by 1. When you pop a value from the stack, you return the top element and then decrement the top.
For example – consider below stack. Initially top were -1. Before pushing 5, increment top = top+1 –top= -1+1 =0, 5 is pushed to the Stack at 0th position. Similarly before pushing 10, top is incremented by 1 and became 0+1 =1 and 10 is pushed at 1st position.
Stack

Stack implementation in Java using Array

Stack implementation in Java using Linked List

Create a Node class which will hold value and link to the next element.

Create the Stack with all the methods.

Next  ↠Queue data structure ↠↠

References:

  • Introduction To Algorithm – CLRS.
  • Algorithm Design Manual – Skiena
  • Data Structure & Algorithms In Java – Robert Lafore