Difference between array linked list stack and Queue

An array is arandom accessdata 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 asequential accessdata 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-calledlimited accessdata structures.

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:pushthe item into the stack, andpopthe 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.pushadds an item to the top of the stack,popremoves 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 arecursivedata 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

Implementation: In the standard library of classes, the data type stack is anadapterclass, 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 implementationby composition.

Another implementation requirement (in addition to the above interface) is that all stack operations must run inconstant 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 variabletopthat refers to the top element in the stack and thecapacitythat refers to the array size. The variabletopchanges from -1 tocapacity – 1. We say that a stack is empty whentop = -1, and the stack is full whentop = capacity-1.

In a fixed-size stack abstraction, the capacity stays unchanged, therefore whentopreachescapacity, the stack object throws an exception. SeeArrayStack.javafor a complete implementation of the stack class. In a dynamic stack abstraction whentopreachescapacity, 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. SeeListStack.javafor a complete implementation of the stack class.

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 allowedenqueueanddequeue. 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 anadapterclass, 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 referencesbackandfront, 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 movesbackreaches 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, untilfront. Such a model is called awrap-around queueor acircular queue.

Finally, whenbackreachesfront, 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.

SeeArrayQueue.javafor a complete implementation of a circular queue.

Applications

The simplest two search techniques are known as Depth-First Search(DFS) 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 webacktrackor 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.

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. Below is the tabular representation of the difference between Array, Stack and Queue:

To watch detailed videos on Data Structures, visit here.

By Yogesh Kumar

Difference between Array and Linked List

Both Linked List and Array are used to store linear data of similar type, but an array consumes contiguous memory locations allocated at compile time, i.e. at the time of declaration of array, while for a linked list, memory is assigned as and when data is added to it, which means at runtime.

Before we proceed further with the differences between Array and Linked List, if you are not familiar with Array or Linked list or both, you can check these topics first:

• Array in C
• Linked List

This is the basic and the most important difference between a linked list and an array. In the section below, we will discuss this in details along with highlighting other differences.

Understanding the Difference Between Array and Linked List

Lesson 49 of 54By Nikita Duggal

PreviousNext

• 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 Understand The Differences Between Stack And Queue

  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 to Learn Depth-First Search(DFS) Algorithm From Scratch

  Lesson - 11

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

  Lesson - 12

  The Definitive Guide to Understand Stack vs Heap Memory Allocation

  Lesson - 13

  All You Need to Know About Linear Search Algorithm

  Lesson - 14

  All You Need to Know About Breadth-First Search Algorithm

  Lesson - 15

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

  Lesson - 16

  The Best Tutorial to Understand Trees in Data Structure

  Lesson - 17

  A Complete Guide to Implement Binary Tree in Data Structure

  Lesson - 18

  A Holistic Look at Using AVL Trees in Data Structures

  Lesson - 19

  All You Need to Know About Tree Traversal in Data Structure

  Lesson - 20

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

  Lesson - 21

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

  Lesson - 22

  The Best and Easiest Way to Understand an Algorithm

  Lesson - 23

  Your One-Stop Solution to Understand Shell Sort Algorithm

  Lesson - 24

  Your One-Stop Solution to Quick Sort Algorithm

  Lesson - 25

  The Most Useful Guide to Learn Selection Sort Algorithm

  Lesson - 26

  Everything You Need to Know About Radix Sort Algorithm

  Lesson - 27

  Everything You Need to Know About the Counting Sort Algorithm

  Lesson - 28

  Everything You Need to Know About the Merge Sort Algorithm

  Lesson - 29

  Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

  Lesson - 30

  Everything You Need to Know About the Bubble Sort Algorithm

  Lesson - 31

  The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

  Lesson - 32

  Your One-Stop Solution to Understand Recursive Algorithm in Programming

  Lesson - 33

  The Definitive Guide to Understanding Greedy Algorithm

  Lesson - 34

  Your One-Stop Solution to Understand Backtracking Algorithm

  Lesson - 35

  The Fundamentals of the Bellman-Ford Algorithm

  Lesson - 36

  Your One-Stop Solution for Graphs in Data Structures

  Lesson - 37

  The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

  Lesson - 38

  A Simplified and Complete Guide to Learn Space and Time Complexity

  Lesson - 39

  All You Need to Know About the Knapsack Problem : Your Complete Guide

  Lesson - 40

  The Fibonacci Series: Mathematical and Programming Interpretation

  Lesson - 41

  The Holistic Look at Longest Common Subsequence Problem

  Lesson - 42

  The Best Article to Understand What Is Dynamic Programming

  Lesson - 43

  A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

  Lesson - 44

  A Holistic Guide to Learn Stop Solution Using Dynamic Programming

  Lesson - 45

  One Stop Solution to All the Dynamic Programming Problems

  Lesson - 46

  Understanding the Fundamentals of Binomial Distribution

  Lesson - 47

  Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

  Lesson - 48

  Understanding the Difference Between Array and Linked List

  Lesson - 49

  The Best Article Out There to Understand the B+ Tree in Data Structure

  Lesson - 50

  A Comprehensive Look at Queue in Data Structure

  Lesson - 51

  Your One-Stop Solution to Understand Coin Change Problem

  Lesson - 52

  The Best Way to Understand the Matrix Chain Multiplication Problem

  Lesson - 53

  Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

  Lesson - 54

Table of Contents