Stack and Queue Introduction

Stack

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it. This structure is used all throughout programming.

The basic implementation of a stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data, since as we will see there are various variations of stack implementations.

There are many real life examples of stack. Consider the simple example of plates stacked over one another in canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.

There are basically three operations that can be performed on stacks. They are 1) inserting an item into a stack (push). 2) deleting an item from the stack (pop). 3) displaying the contents of the stack (peep).

Below are some of operations a stack data type normally supports:

Stack<item-type> Operations

push(new-item:item-type)

Adds an item onto the stack.

top():item-type

Returns the last item pushed onto the stack.

pop()

Removes the most-recently-pushed item from the stack.

is-empty():Boolean

True if no more items can be popped and there is no top item.

is-full():Boolean

True if no more items can be pushed.

get-size():Integer

Returns the number of elements on the stack.

Applications of Stacks

• Converting a decimal number into a binary number
• Expression evaluation and syntax parsing
• Quicksort
• An algorithm that has Linear Time Complexity
• Balancing of symbols
• Infix to Postfix /Prefix conversion
• Redo-undo features at many places like editors, photoshop.
• Forward and backward feature in web browsers
• Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
• Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and Sudoku solver

 

Queue

A queue is a linear list of elements in which deletion of an element can take place only at one end called the front and insertion can take place on the other end which is termed as rear. The term front and rear are used frequently while describing queues in a linked list. In this chapter you will deal with queue as arrays.

In the concept of queue, the first element to be inserted in the queue will be the first element to be deleted or removed from the list. So Queue is said to follow the FIFO (First In First Out) or FCFS (First Come First Serve) structure. A real life scenario in the form of example for queue will be the queue of people waiting to accomplish a particular task where the first person in the queue is the first person to be served first.

A queue is also called a FIFO (First In First Out) to demonstrate the way it accesses data.

Types of Queue

• Simple Queue
• Circular Queue
• Dequeue

Queue<item-type> Operations

enqueue(new-item:item-type)

Adds an item onto the end of the queue.

front():item-type

Returns the item at the front of the queue.

dequeue()

Removes the item from the front of the queue.

is-empty():Boolean

True if no more items can be dequeued and there is no front item.

is-full():Boolean

True if no more items can be enqueued.

get-size():Integer

Returns the number of elements in the queue.

Circular Queue

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.

Applications of Queue

Queue is used when things don’t have to be processed immediately, but have to be processed in First In First Out order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios.

1)      When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.

2)      When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Applications of Circular Queue

1)      Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.

2)      Traffic system: In computer controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.

3)      CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.