Data Structure: Stack and Queue

 

Stack and Queue in Data Structure

WHAT IS STACK ?

A linear data structure is a stack. A LIFO (Last In First Out) data structure is a stack. The first element that can be deleted from a stack is the last element that was added. Only one side of the list, termed the top, can have elements added or removed.

Pushing is the process of adding an element to a stack. Popping is the process of removing an element from a stack. A pointer called top is used to monitor the last entry in a list in stacks.

Stack Implementation:

1)      Using array
2)      Using linked list

Array: It's a random-access container, which means that any part of it can be accessed at any time.

Linked: A linked list is a collection of related items. It's a sequential-access container, which means that the data structure's elements can only be accessed in that order.

On the stack, the following operations are performed:

• create(): creates a new object. To build a stack with a small number of parts

 • push(): Adds a new element to the stack.

 • pop(): a method for removing an element from a stack.

 • traverse(): This method displays the stack's elements.

 • isempty(): Determines whether the stack is empty or not.

 • isfull(): Determines whether the stack is full or not.

• sizeof(): Stack size

 Stack-based operations

 create operation on the stack .

 To make an empty stack, go through the steps listed below.

  Step 1: Include all of the program's header files and create a constant'size' with a defined value.

 Step 2: Declare all of the functions that will be utilised to implement the stack.

Step 3: Make a fixed-size one-dimensional array.

Step 4: Create an integer variable called 'top' and set its value to '-1'.

Step 5: In the main method, display a menu with a list of operations and utilise appropriate function calls to conduct the operation on the stack that the user has selected.

int stack[6];      

Push operation on the stack ()

Inserting an element onto the stack is referred to as a push operation. The new element is inserted at the top of the stack since there is only one position where it may be positioned – the top of the stack. You can use the push() method to add one or more elements to the end of an array. The length property, which indicates the amount of elements in the array, is returned by the push() method. 

The following are the steps for a push operation:

 Step 1: Make sure the stack isn't overflowing. (size-1 == top)

 Step 2: If the stack is full, the message 'Stack is full!' will be displayed. 'Insertion is not feasible!' and the function is terminated.

Step 3: If the stack[top] is not empty, delete it and reduce the top value by one (top—).

Operation on stack: pop()

Pop operation refers to the removal of an element. Again, since we only have access to the element at the top of the stack, there’s only one element that we can remove. We just remove the top of the stack. We can also choose to return the value of the popped element back, its completely at the choice of the programmer to implement this.

Step 1: Check whether stack is empty(top == -1).

Step 2: If it is empty, then display 'Stack is empty! Deletion is not possible!' and terminate the function.

Step 3: If it is not empty, then delete stack[top] and decrement top value by one (top--).

Position of Top	Status of Stack
-1	Stack is Empty
0	Only one element in Stack
N-1	Stack is Full
N	Overflow state of Stack

 

Complexity Analysis of Stack Operations

Below mentioned are the time complexities for various operations that can be performed on the Stack data structure.

Push Operation : O(1)

Pop Operation : O(1)

Top Operation : O(1)

The time complexities for push() and pop() functions are O(1) because we always have to insert or remove the data from the top of the stack, which is a one step process.

How to understand stack practically?

Plates

A real-life stack example...

 A most popular example of stack is plates in marriage party. Fresh plates are pushed onto to the top and popped from the top.

Building Floors: If a person lives on the top level and wants to walk outside, he or she must first go to the first floor.

WHAT IS QUEUE ?

WHAT DOES IT MEAN TO BE IN A QUEUE?

A queue is a linear data structure or an abstract data type. A FIFO (First In First Out) data structure is a queue. The first element in a queue is the first one to be removed. Only one side of the list, called the back (sometimes known as the tail), may be used to insert elements, and only the other side, called the front, can be used to delete them (also called head).

An enqueue operation is when an element is added to a queue, and a dequeue operation is when an element is removed from the queue. Two pointers are maintained for queues;

1. The front pointer refers to the element that was inserted first and is still in the list.

2. The element is pointed at by the rear pointer.

Implementation of queue:

1)Using array

2)Using linked list

       Array:- When a queue is implemented using array, that queue can organize only limited number of elements.           

       Linked list:- When a queue is implemented using linked list, that queue can organize unlimited number of elements.     

 When a queue is implemented using an array, it can only organise a certain number of elements.

Linked list: A queue that is implemented using a linked list can organise an infinite amount of elements.

Queue-based operations

Initializing or establishing the queue, using it, and finally entirely wiping it from memory are examples of queue operations.

Remove an item from the queue with dequeue().

To display the queue's elements, use the display() method.

peek() returns the first element in the queue without removing it.

isfull() determines whether the queue is full.

isempty() determines whether the queue is empty.

   

• 
  

Operation on queue: dequeue()

Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation −

• Step 1 − Check if the queue is empty.

• Step 2 − If the queue is empty, produce underflow error and exit.

• Step 3 − If the queue is not empty, access the data where front is pointing.

• Step4 − Increment front pointer to point to the next available data element.

             Step 5 − Return success.

Complexity Analysis of Queue Operations

Just like Stack, in case of a Queue too, we know exactly, on which position new element will be added and from where an element will be removed, hence both these operations requires a single step.

• Enqueue: O(1)
• Dequeue: O(1)

How to understand queue practically?

A real-life stack example...

a single-lane one-way road, where the 

vehicle enters first, exits first.

Thanks for reading!

Do leave  your feedback and share what you feel about this blog….