Data Structures: Lecture 6

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203 

Faculty        : Avinash Kumar

Syllabus covered in  this blog

STACK (Introduction, Operations) 

Stack

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc. A real-world stack allows operations at one end only. 

For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.

This feature makes it LIFO(Last-in-first-out) data structure. Here, the element which is inserted last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.

Basic Operations

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations −

·        push() − Pushing (storing) an element on the stack.

·        pop() − Removing (accessing) an element from the stack.

To use a stack efficiently, we need to check the status of stack. For the same purpose, the following functionality is added to stacks −

·        peek() − get the top data element of the stack, without removing it.

·        isFull() − check if stack is full.

·        isEmpty() − check if stack is empty.

We maintain a pointer to that always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.

Push Operation

The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps −

·        Step 1 − Checks if the stack is full.

·        Step 2 − If the stack is full, produces an error and exit.

·        Step 3 − If the stack is not full, increments top to point next empty space.

·        Step 4 − Adds data element to the stack location, where top is pointing.

·        Step 5 − Returns success.

Algorithm for PUSH Operation:

push:(stack, data) 

   if stack is full

      return null     

   top = top + 1

   stack[top] = data

Example

void push(int data)

{

   if(!isFull())

   {

      top = top + 1;   

      stack[top] = data;

   } 

   else 

   {

      cout<<"Could not insert data, Stack is full.\n";

   }

}

Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.

A Pop operation may involve the following steps:

•  Step 1 − Checks if the stack is empty.
•  Step 2 − If the stack is empty, produces an error and exit.
• Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
•  Step 4 − Decreases the value of top by 1.
• Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

pop: (stack) 

   if stack is empty

      return null      

   data = stack[top]

   top = top - 1

   return data 

Example

int pop(int data) 

{

   if(!isempty()) 

   {

      data = stack[top];

      top = top - 1;   

      return data;

   } 

   else 

   {

      cout<<"Could not retrieve data, Stack is empty.\n";

   }

}