The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Stacks & Queues

Problem :-
Implement a stack using an array. Write the following functions :
push ( int ) to insert an element on top of stack.
pop ( ) to remove the top element from stack.
topElement ( ) to get the top element of stack.
display ( ) to display all the elements of stack.

Solution :-
We will maintain an array of fixed size and a variable top which stores the index of the last element in the array. For inserting ( pushing ) an element, top is incremented and element is inserted. For removing ( popping ) an element, top is decremented. See the implementation below.

#include<iostream>
#define SIZE 100
#define NO_ELEMENT -999999
using namespace std;

class Stack {
   int arr[SIZE]; // array to store Stack elements
   int top;
public:
   Stack() {
      top = -1;
   }
   void push(int); // push an element into Stack
   void pop(); // pop the top element from Stack 
   int topElement(); // get the top element
   void display(); // display Stack elements from top to bottom
};

void Stack :: push(int data) {
   if (top == SIZE) { // no space in Stack
      cout << "Stack Overflow ... " << endl;
      return;
   }
   else {
      top++; // increment top
      arr[top] = data; // insert the data onto top of Stack
   }
}

void Stack :: pop() {
   if (top == -1) { // Stack is empty
      cout << "Stack is empty ... " << endl;
   }
   else {
      top--; // decrement top (remove the top element)
   }
}

int Stack :: topElement() {
   if (top == -1) { // Stack is empty
      return NO_ELEMENT;
   }
   else {
      return arr[top];
   }
}

void Stack :: display() {
   cout << "Displaying Stack Elements :- " << endl;
   int i;
   for (i = top; i >= 0; i--) {
      cout << arr[i] << " ";
   }
   cout << endl;
}

int main() {
   Stack s;
   s.push(12);
   s.push(5);
   s.push(13);
   s.display();
   cout << "Top Element : " << s.topElement() << endl;
   s.pop(); // removing the top element i.e 13  
   s.push(7);
   s.display();
   return 0;
}

Back | Next

All problems on Stacks and Queues
* Implement a stack using an array
* Implement a queue using an array
* Implement a circular queue using an array
* Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity
* Implement a circular queue using linked list
* Implement a Queue data structure using two stacks
* Sort a Queue using two stacks
* Convert infix expression to the postfix notation
* Implement an algorithm to evaluate a postfix expression
* Given a stack with only 0s & 1s, find the majority element in the stack
* Implement an inplace algorithm to sort a stack