03-08-2012, 01:47 PM
Stacks and Queues
1Stacks and Queues.ppt (Size: 547 KB / Downloads: 181)
Abstract Data Type
Abstract Data Type as a design tool
Concerns only on the important concept or model
No concern on implementation details.
Stack & Queue is an example of ADT
An array is not ADT.
What is the difference?
Stack & Queue vs. Array
Arrays are data storage structures while stacks and queues are specialized DS and used as programmer’s tools.
Stack – a container that allows push and pop
Queue - a container that allows enqueue and dequeue
No concern on implementation details.
In an array any item can be accessed, while in these data structures access is restricted.
They are more abstract than arrays.
Stack operations
Placing a data item on the top is called “pushing”, while removing an item from the top is called “popping” it.
push and pop are the primary stack operations.
Some of the applications are : microprocessors, some older calculators etc.
Queues
Queue is an ADT data structure similar to stack, except that the first item to be inserted is the first one to be removed.
This mechanism is called First-In-First-Out (FIFO).
Placing an item in a queue is called “insertion or enqueue”, which is done at the end of the queue called “rear”.
Removing an item from a queue is called “deletion or dequeue”, which is done at the other end of the queue called “front”.
Some of the applications are : printer queue, keystroke queue, etc.
Circular Queue
When a new item is inserted at the rear, the pointer to rear moves upwards.
Similarly, when an item is deleted from the queue the front arrow moves downwards.
After a few insert and delete operations the rear might reach the end of the queue and no more items can be inserted although the items from the front of the queue have been deleted and there is space in the queue.
To solve this problem, queues implement wrapping around. Such queues are called Circular Queues.
Both the front and the rear pointers wrap around to the beginning of the array.
It is also called as “Ring buffer”.
Items can inserted and deleted from a queue in O(1) time.