What are stacks?

Stacks are programmatic data structures that allow access to only one item at a time, the last item inserted. Stacks internally use other data structures such as arrays for their implementation. A stack is a Last-In-First-Out (LIFO) storage mechanism, because the last item inserted is the first to be removed.

What are the key public interfaces provided by Stacks?

Stacks usually provide the following key interfaces.

push() - Inserts a new data item on the top of the stack.

pop() - Removes the item from the top of the stack

peek() - Returns the item from the top of the stack without removing it.

isFull() - Returns true if the stack is full.

isEmpty() - Returns true if the stack is empty.

Write a program to implement stack functionality?

Following Java program implements the stack functionality. It internally uses an array for the implementation.

class MyStack {

 private int maxSize;
 private int[] stackArray;
 private int top; //constructor
 public MyStack(int maxSize) {
  this.maxSize = maxSize;
  stackArray = new int[maxSize];
  top = -1;
 }

 //push an item to stack
 public void push(int i) {
  //increment top and insert item
  stackArray[++top] = i;
 }

 //remove an item from stack
 public void pop() {
  //return item and decrement top
  return stackArray[top--] = i;
 }

 //view item from top of stack
 public void peek() {
  return stackArray[top];
 }

 //check if stack is empty
 public void isEmpty() {
  return (top == -1);
 }

 //check if stack is full
 public void isFull() {
  return (top == maxSize);
 }
}

What is the time efficiency of the push() and pop() operations of stacks?

The push() and pop() methods implemented in stacks take constant time to execute. i.e. the time to execute is very quick and is not dependent on the number of items on the stack. In Big O notation this is represented as O(1).

What are some common scenarios where stacks are used?

Following are some of the common scenarios in which Stacks can be Used.

- To check if delimiters (parenthesis, brackets etc.) are balanced in a computer program

- To reverse strings

- To traverse the nodes of a binary tree.

- To search the vertices of a graph.

- To process tasks

- To process messages