Table of contents

Introduction

Stacks

2.1.

Applications

2.1.1.

Backtracking

2.1.2.

Language Processing

2.1.3.

Arithmetic Expression Evaluation

2.1.4.

Evaluating a Postfix Expression

2.2.

Implementation

2.3.

Linked List base Implementation

Queues

3.1.

Implementation

3.2.

Circular Queue

3.3.

Applications

3.3.1.

Depth-First Search with a Stack

3.3.2.

Breadth-First Search with a Queue

Frequently Asked Questions

4.1.

Name some applications of queue Data Structure.

4.2.

What is the time complexity of push and pop functions of queues?

4.3.

What is the main advantage of using an array?

4.4.

What is the main disadvantage of using an array?

Conclusion

Last Updated: Mar 27, 2024

Medium

Difference between Array, Queue & Stack

Author Shreya Deep

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

An array is a random access data structure, where each element can be accessed directly and in constant time. A typical illustration of random access is a book – each page of the book can be open independently of others. Random access is critical to many algorithms, for example, binary search.

A linked list is a sequential access Data Structure, where each element can be accessed only in a particular order. A typical illustration of sequential access is a roll of paper or tape – all prior material must be enrolled in order to get to data you want. In this note, we consider a subcase of sequential data structures, so-called limited access data structures.

Also See, Array Implementation of Queue and Rabin Karp Algorithm

Stacks

A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure – elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

A stack is a recursive data structure. Here is a structural definition of a Stack: A stack is either empty or it consists of a top and the rest which is a stack.

Applications

The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack
Another application is an “undo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack

Backtracking

This is a process when you need to access the most recent data element in a series of elements. Think of a labyrinth or maze – how do you find a way from an entrance to an exit? Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Therefore, at each choice point, you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack.

Language Processing

Space for parameters and local variables is created internally using a stack
Compiler’s syntax check for matching braces is implemented by using stack
Support for recursion

Arithmetic Expression Evaluation

An important application of stacks is in parsing. For example, a compiler must parse arithmetic expressions written using infix notation:

1 + ((2 + 3) * 4 + 5)*6

We break the problem of parsing infix expressions into two stages. First, we convert from infix to a different representation called postfix. Then we parse the postfix expression, which is a somewhat easier problem than directly parsing infix. Converting from Infix to Postfix. Typically, we deal with expressions in infix notation

2 + 5

where the operators (e.g. +, *) are written between the operands (e.q, 2 and 5). Writing the operators after the operands give a postfix expression 2 and 5 are called operands, and the ‘+’ is the operator. The above arithmetic expression is called infix since the operator is in between operands. The expression

2 5 +

Writing the operators before the operands gives a prefix expression

+2 5

Suppose you want to compute the cost of your shopping trip. To do so, you add a list of numbers and multiply them by the local sales tax (7.25%):

70 + 150 * 1.0725

Depending on the calculator, the answer would be either 235.95 or 230.875. To avoid this confusion we shall use a postfix notation

70 150 + 1.0725 *

Postfix has the nice property that parentheses are unnecessary.

Now, we describe how to convert from infix to postfix.

Read in the tokens one at a time
If a token is an integer, write it into the output
If a token is an operator, push it to the stack, if the stack is empty. If the stack is not empty, you pop entries with higher or equal priority and only then you push that token to the stack
If a token is a left parentheses ‘(‘, push it to the stack
If a token is a right parentheses ‘)’, you pop entries until you meet ‘(‘
When you finish reading the string, you pop up all tokens which are left there
Arithmetic precedence is in increasing order: ‘+’, ‘-‘, ‘*’, ‘/’;

Example: Suppose we have an infix expression:2+(4+3*2+1)/3. We read the string by characters.

‘2’ – send to the output

‘+’ – push on the stack

‘(‘ – push on the stack

‘4’ – send to the output

‘+’ – push on the stack

‘3’ – send to the output

‘*’ – push on the stack

‘2’ – send to the output

Evaluating a Postfix Expression

We describe how to parse and evaluate a postfix expression.

We read the tokens in one at a time
If it is an integer, push it on the stack
If it is a binary operator, pop the top two elements from the stack, apply the operator, and push the result back on the stack

Consider the following postfix expression

5 9 3 + 4 2 * * 7 + *

Here is a chain of operations

Note, that division is not a commutative operation, so 2/3 is not the same as 3/2.

Implementation

In the standard library of classes, the data type stack is an adapter class, meaning that

a stack is built on top of other data structures. The underlying structure for a stack could be an array, a vector, an ArrayList, a linked list, or any other collection. Regardless of the type of the underlying data structure, a Stack must implement the same functionality. This is achieved by providing a unique interface.

The following picture demonstrates the idea of implementation by composition.

Another implementation requirement (in addition to the above interface) is that all stack operations must run in constant time O(1). Constant time means that there is some constant k such that an operation takes k nanoseconds of computational time regardless of the stack size.

In an array-based implementation, we maintain the following fields: an array A of default size (≥ 1), the variable top that refers to the top element in the stack and the capacity that refers to the array size. The variable top changes from -1 to capacity – 1. We say that a stack is empty when top = -1, and the stack is full when top = capacity-1.

In a fixed-size stack abstraction, the capacity stays unchanged, therefore when top reaches capacity, the stack object throws an exception. In a dynamic stack abstraction when top reaches capacity, we double up the stack size.

Linked List base Implementation

Linked List-based implementation provides the best (from the efficiency point of view) dynamic stack implementation.

Also see, Morris Traversal for Inorder.

You can also read Difference Between Array List and Linked List here.

Also read about - hash function in data structure

Queues

A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in-first-out (FIFO) principle. An excellent example of a queue is a line of students in the food court of the UC. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue, only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access.

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Implementation

In the standard library of classes, the data type queue is an adapter class, meaning that a queue is built on top of other data structures. The underlying structure for a queue could be an array, a Vector, an ArrayList, a LinkedList, or any other collection. Regardless of the type of the underlying data structure, a queue must implement the same functionality. This is achieved by providing a unique interface.

interface QueueInterface‹AnyType>
{
public boolean isEmpty();
public AnyType getFront();
public AnyType dequeue();
public void enqueue(AnyType e);
public void clear();
}

Each of the above basic operations must run at constant time O(1). The following picture demonstrates the idea of implementation by composition.

Circular Queue

Given an array A of default size (≥ 1) with two references back and front, originally set to -1 and 0 respectively. Each time we insert (enqueue) a new item, we increase the back index; when we remove (dequeue) an item – we increase the front index. Here is a picture that illustrates the model after a few steps:

As you see from the picture, the queue logically moves in the array from left to right. After several moves back reaches the end, leaving no space for adding new elements.

However, there is a free space before the front index. We shall use that space to enqueue new items, i.e. the next entry will be stored at index 0, then 1, until front. Such a model is called a wrap-around queue or a circular queue.

Finally, when back reaches front, the queue is full. There are two choices to handle a full queue:a) throw an exception; b) double the array size.

The circular queue implementation is done by using the modulo operator (denoted %), which is computed by taking the remainder of division (for example, 8%5 is 3). By using the modulo operator, we can view the queue as a circular array, where the “wrapped around” can be simulated as “back % array_size”. In addition to the back and front indexes, we maintain another index: cur – for counting the number of elements in a queue. Having this index simplifies a logic of implementation.

Must Read Stack Operations

Applications

The simplest two search techniques are known as Depth-First Search(DFS Algorithm) and Breadth-First Search (BFS). These two searches are described by looking at how the search tree (representing all the possible paths from the start) will be traversed.

Depth-First Search with a Stack

In depth-first search we go down a path until we get to a dead-end; then we backtrack or back up (by popping a stack) to get an alternative path.

Create a stack
Create a new choice point
Push the choice point onto the stack
While (not found and the stack is not empty)
- Pop the stack
- Find all possible choices after the last one tried
- Push these choices onto the stack
Return

Breadth-First Search with a Queue

In breadth-first search, we explore all the nearest possibilities by finding all possible successors and enqueue them to a queue.

Create a queue
Create a new choice point
Enqueue the choice point onto the queue
While (not found and queue is not empty)
- Dequeue the queue
- Find all possible choices after the last one tried
- Enqueue these choices onto the queue
Return

We will see more on search techniques later in the course.

Below is the tabular representation of the difference between Array, Stack and Queue:

QUEUES	ARRAY	STACK
Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.	In the array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location within the square bracket.	Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list.
Insertion and deletion in Queues takes place only from rear and front respectively.	Insertion and deletion in array can be done at any index in the array.	Insertion and deletion in stacks take place only from one end of the list called the top.
Queue has a dynamic and fixed size.	Array has a fixed size.	Stack has a dynamic and fixed size.
Queue can contain elements of different data type.	Array contains elements of same data type.	The stack can contain elements of the different data types.
Different types of Queues are circular queue, priority queue, doubly ended queue.	Different types of Arrays are 1D, 2D, etc.	Stack has only one type.

To watch detailed videos on Data Structures, visit here.

Read about Application of Queue in Data Structure here.

Must Read Algorithm Types

Frequently Asked Questions

Name some applications of queue Data Structure.

To keep the playlist in media players (to add or remove the songs)
To reverse strings
To verify if delimiters (parenthesis, brackets etc.) are balanced in a computer program
To search the vertices of a graph.

What is the time complexity of push and pop functions of queues?

The time complexity of enqueue is O(1) and the time complexity of Dequeue is O(n).

What is the main advantage of using an array?

By using the array, accessing an element is easy using the index number.

What is the main disadvantage of using an array?

The main disadvantage of the array is that you cannot increase the size of the array after the creation of the array.

Conclusion

In this article, we learned about the differences between arrays, queues, and stacks. We hope that you've enjoyed reading this article and were able to understand the concepts explained. You can check out some more articles from the Coding Ninjas Studio platform. For example:

Recommended problems -

You can also consider our Mern Stack Course to give your career an edge over others.

Happy learning!