Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide to Stacks and Queues Data Structures

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 11

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 12

All You Need to Know About Linear Search Algorithm

Lesson - 13

All You Need to Know About Breadth-First Search Algorithm

Lesson - 14

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 15

The Best Tutorial to Understand Trees in Data Structure

Lesson - 16

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 17

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 18

All You Need to Know About Tree Traversal in Data Structure

Lesson - 19

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 20

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 21

Your One-Stop Solution for Graphs in Data Structures

Lesson - 22
The Ultimate Guide to Stacks and Queues Data Structures

Stacks and queues are the fundamental Data Structures used in day-to-day programming applications. A stack is the linear data structure that follows the LIFO (Last In First Out), and insertion and deletion operation is done from only one end of the stack. Queue data structure follows the FIFO (First In First Out) principle, where insertion is done at one end and deletion is done at the other end.

What is Stack?

Both Stacks and Queues are Linear Data Structures, but there is a slight difference between them both. You will understand them in detail through their definitions. First, you will get to know stacks.

Stacks are the linear data structure that follows the LIFO (Last In First Out) or FILO (First In Last Out) principle in which it performs all operations. Here are some real-life examples of the stack, which are stacks of books, papers, etc.

stack-of-book.

stack-of-papers.

These examples allow some operation like insertion of books and removal of papers only from one end, that is top of the book and the top of the paper stacks. Similarly, in a stack data structure at any given point in time, you can access only the top of the stacks.

Moving forward in the topic of Stacks and Queues, you will understand the Representation of Stacks.

Representation of Stacks

There is a slight difference between the representation of stacks and queues in memory. You will see the representation of the stack first.

The following diagram depicts a representation of the stack. As you read earlier, stacks follow LIFO order, and you can access them only from the top of the stack.

stack-representation1.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Basic Operations on Stacks

Both Stacks and Queues can perform some of the fundamental operations, like storing and manipulating the data elements. Now, you will understand the functions of the stack.

You can perform some basic operations on the stacks, they are:

push():

Inserting or adding a data element from the top of the stack is known as a push operation.

Push operation involves the following steps:

Step 1: Checks if the stack is complete or not.

Step 2: If the stack is complete, it will exit and produce an overflow condition.

Step 3: If the stack is not complete, it increments the top by one and points to the next space.

Step 4: Adds data element to that space 

Step 5: Returns as a success

push-operation-on-stack.

Algorithm of the Push Operation:

begin :stack, data_element

 If the stack is full 

  return null

end if

top <- top + 1

stack[top] = data_element

end

Example of a Push Operation:

void push(int data_element){

if(!isfull()) {

top = top + 1;

stack[top] = data_element;

}

else{

printf(‚Äú Stack is already full‚ÄĚ);

}

} 

Pop ():

Removing data elements from the stack from the top of the stack is known as pop operation.

The pop operation also includes some steps, which are as follows:

Step 1: Checks if the stack is empty or not.

Step 2: If the stack is already empty, it exits and produces an underflow condition.

Step 3: When the stack is not empty, it then accesses the topmost data element.

Step 4: Decreases the value of the top by one.

Step 5: Returns as a success.

pop-operation-on-stack.

Algorithm of a Pop Operation:

begin pop: Stack

if the stack is empty

  return null

end if

data_element <- stack[top]

top <-top - 1

return data_ element

end

Example of Pop Operation:

int pop(int data_element){

if(isempty()) {

data_element = stack[top];

top = top - 1;

return data_elemnt;

} else {

printf(‚Äú stack is already empty‚ÄĚ)

}

}

Peek ():

It involves retrieving the topmost data element from the stack without removing it from the stack's data elements.

Algorithm of a Peek Operation:

begin 

return stack[top]

end

Example of a Peek Operation:

int peek()

{

 return stack[top];

}

isfull():

This operation is used to check whether or not the stack is complete.

Algorithm of an isfull() Operation:

Max_Size is the maximum size of the stack.

begin

If top equals to Max_Size

  return true

else 

  return false

end if

end

Example of an isfull() Operation:

bool isfull(){

 if( top == Max_Size)

 return true;

else

 return false;

}

isempty():

The isEmpty method is used to check whether the stack is empty or not.

Algorithm of an isempty() Operation:

Begin 

If the top is less than -1

 Return true

Else

 Return false

End if

end

Example of an isempty() Operation:

bool isempty(){

if ( top ==  -1)

 return true;

else

 return false;

}

Stacks Implementation 

Stacks and Queues might look similar, but there is a significant difference in the implementation. Now, you will learn about stack data structure implementation. The implementation of the stacks is done in two ways:

  • Stack implementation using an array.

stack-implementation-using-an-array

  • Stack implementation using linked-list.

stack-implementation-using-linked-list.

The Stacks and Queues are applied for various computational purposes. This tutorial will now discuss the applications of stacks:

  • The stacks are used for expression evaluation
  • The stacks are used for parentheses checking expressions
  • Stacks are used to convert expressions from one form to another
  • The stacks can be used as backtracking
  • Tower of Hanoi is the best use of stacks
  • Memory management and function are the application of stacks
  • The stacks are also used for string reversal

What is the Queue?

The queues are the linear data structure that follows the principle FIFO (First in, first out), and all the operations are performed according to this principle only. Consider this example, here customers in the supermarket form a queue to make their payment based on who comes first, and is served first.

example-of-queue

Unlike stacks, queues allow it to perform its operation from two ends. One end consistently inserts data known as enqueue, and one end removes the data element known as dequeue.

Next, in the stacks and queues data structure tutorial, you will learn about the representation of queue data structure.

Representation of Queues

The representation of stacks and queues is almost similar. However, there is a slight difference. In this section, you will learn about the representation of stacks.

Here, you already figured out how you can represent the queue. You can access the queue from the end, as shown in this diagram. From one end, it inserts data elements, and it removes them from another end.

queue-representation.

Basic Operations 

As you saw before, you can perform data manipulation operations both on stacks and queues. Here, you will learn the operations to be performed on the queue. Now, try to understand some fundamental operations of queue data structure:

Peek() Operation:

In the peek operation, you try to get the data element at the front without removing it from the queue.

The Algorithm of the "Peek" Operation Is as Follows:

begin to peek

return queue[ front ]

end

The Example of a Peek Operation Is as Follows:

int peek(){

return  queue[front];

}

isfull() Operation:

This operation is performed to check whether or not the queue is full.

The Algorithm of the isfull Operation Is as Follows:

Here MAXSIZE determines the maximum size of the queue. 

Begin isfull

Begin isfull

if rear equals MAXSIZE

   return true

else 

  return false

end if

end

Example of an isfull Operation

bool isfull()

{

 If (rear== MAXSIZE-1)

 return true;

 else

 return false;

}

isempty() Operation:

The Isempty operation is performed to check whether the queue is empty or not.

The Algorithm of the isempty Operation Is as Follows:

Begin isempty

If the front is less than min or the front is greater than the rear

 return true

else

 return false

end if

end

The Example of an isempty Operation

bool isempty()

{

 if ( front< 0 || front > rear)

 return true;

else

 return false;

}

Enqueue Operation:

Enqueue refers to inserting or adding some data element to the queue. You always insert an element with the help of a rear pointer.

Enqueue operation includes two pointers, REAR, and FRONT. Following are some steps for the same:

Step 1: Verify whether the queue is full or not.

Step 2: If the queue is full already, exit and produce an overflow condition.

Step 3: If the stack is not complete, increment the rear and point to space.

Step 4: Add the data element where the rear is pointing.

Step 5: Success.

queue-enqueue.

Algorithm of Enqueue Operation:

Begin enqueue(data_element)

 If the queue is full

 Overflow

end if

 rear <- rear +1

 queue[rear] = data_element

 return true

end

Example of Enqueue Operation:

int enqueue( int data_element)

if (isfull())

 return 0;

rear= rear + 1;

queue[rear] = data_element;

return 1;

Dequeue Operation:

Dequeue refers to delete or remove data elements from the queue, and you use a front pointer to do this operation.

Dequeue operation includes the following steps:

Step 1: Check if the queue is empty or not.

Step 2: If the queue is the empty exit and if it does produce an underflow condition.

Step 3: Queue is not empty, then access the data where the front is pointing and remove that data element from the queue.

Step 4: Increment front to point to the next existing data element

Step 5: Return success.

queue-dequeue.

Algorithm of the Dequeue Operation:

Begin

if the queue is empty

 Return underflow

End if

data_element = queue[front]

front <- front +1

return true

end

Example of a Dequeue Operation:

int dequeue() {

 if ( isempty() )

  return 0;

int data_element = queue[front];

front = front + 1;

 return data_element;

 }

In the next section of the stacks and queues tutorial, you will learn about the implementation of a queue.

Stand Out From Your Peers this Appraisal Season

Start Learning With Our FREE CoursesEnroll Now
Stand Out From Your Peers this Appraisal Season

Queues Implementation

Implementation of the queues can be done in two ways:

  • Implementation of a queue using an array

implementation-of-queue-using-array

  • Implementation of queue using a linked-list

queue-implementation-using-linked-list.

So far in this Stacks and Queues tutorial, you learned the implementation of queues. Now you will look into the Types of Queues.

Types of Queues

There are three types of queue data structures:

  1. Circular Queue
  2. Dequeue (Double Ended Queue)
  3. Priority Queue

Circular Queue

  • The end node of the circular queue is connected to the first node
  • A circular queue is also called a Ring Buffer

circular-queue.

Dequeue (Double Ended Queue)

In the double-ended queue, you can perform insertion and deletion on both ends that are rear as well as the front.

double-ended-queue

Priority Queue

  • Every node has some predefined priority in the priority queue
  • The node having the least priority will be the first which is removed from the queue
  • Insertion in the priority queue is done as the arrival of node.

priority-queue

In the next section of the Stacks and Queues tutorial, you will learn the application of queues in real-time.

Application of Queues

  • CPU scheduling and disk scheduling, where one resource is shared among various consumers
  • IO Buffers, files, and Pipes IO, where data is transferred asynchronously between two processes
  • Semaphores in the operating system
  • FCFS (First Come First Serve) scheduling
  • Spooling in printers
  • Queue in routers and switches in networking
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

So with that, you have come to an end of this "Stacks and Queues" tutorial. "Tree in Data Structure" can be your next topic to learn. The tree data structure is non-linear, represented by nodes and each node connected with edges. You will explore tree traversal, which is of three types which is preorder, inorder and postorder.

If you are perhaps looking to build a career in software development, explore different offerings from Simplilearn in Software Development. These programs will give you the work-ready software development training you need to succeed today. 

If you have any queries regarding this "Stacks and Queues" tutorial, please feel free to ask in the comment section. Our experts will be happy to solve all your questions ASAP!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.