Note 3: Stack
and Queue Concept in Data Structure for Application
Stack:
It is a sequence of items that are accessible at only one end of the sequence. Think of a stack as a collection of items that are piled one on top of the other, with access limited to the topmost item. A stack inserts item on the top of the stack and removes item from the top of the stack. It has LIFO (last-in / first-out) ordering for the items on the stack.
Type of Stack:
Linked List Stack
Operation of Stack:
Add: a push( ) operation adds an item to the topmost location on the stack.
Push
function:
void push ( short stack[], short stack_size, short top, short item)
{
if ( top >= stack_size 1)
{
cout << The stack is full! << endl;
return;
}
stack[+ + top] = item;
}
Delete: a pop( ) operation removes an item from the topmost
location on the stack 
Pop function:
short pop (short stack[], short stack_size, short top)
{
if ( top = = 1)
{
cout << The stack is empty! << endl;
return 0;
}
return stack[top ] ;
}
Queue:
A queue is a sequential storage structure that permits access only at the two ends of the sequence. We refer to the ends of the sequence as the front and rear. A queue inserts new elements at the rear and removes elements from the front of the sequence. You will note that a queue removes elements in the same order in which they were stored, and hence a queue provides FIFO (first-in / first-out), or FCFS (first-come / first-served), ordering.
Operation of Queue:
Add: insert operation for the queue is adding item to the new element at the rear of queue.
Delete: remove operation for the queue is deleting item from the front element of queue.
The non-circular queue with 8 elements:
Algorithms:
Variables:
short qfront = -1, qrear = -1, qsize = 8;
Insert:
Delete:
Graphical Presentation:
The circular queue with 8 elements:
Algorithms:
Variables:
short qfront = 0, qcount = 0, qsize = 8;
Insert:
Delete:
Graphical Presentation:
|
Structure Type |
Array |
Link List |
Link List Array |
|
Stacks |
Linear Stacks |
Linear Stacks |
Linear Stacks |
|
Queue |
Non-Circular Queue Circular Queue Priority Queue |
Non-Circular Queue Circular Queue Priority Queue |
Non-Circular Queue Circular Queue Priority Queue |
Multiple Stacks and Queues:
Multiple Stacks:
Following pictures are two ways to do two stacks in array:
1. None fixed size of the stacks:
v Stack 1 expands from the 0th element to the right
v Stack 2 expands from the 12th element to the left
v As long as the value of Top1 and Top2 are not next to each other, it has free elements for input the data in the array
v When both Stacks are full, Top1 and Top 2 will be next to each other
v There is no fixed boundary between Stack 1 and Stack 2
v Elements 1 and 2 are using to store the information needed to manipulate the stack (subscript for Top 1 and Top 2)
v Elements 1 and 2 are using to store the size of Stack 1 and the subscript of the array for Top 1 needed to manipulate Stack 1
v Elements 3 and 4 are using to store the size of Stack 2 and the subscript of the array for Top 2 needed to manipulate Stack 2
Multiple Queues:
Following pictures are two ways to do two queues in array:
1. None fixed size of the queues:
v Queue 1 expands from the 0th element to the right and circular back to the 0th element
v Queue 2 expands from the 8th element to the left and circular back to the 8th element
v Temporary boundary between the Queue 1 and the Queue 2; as long as there has free elements in the array and boundary would be shift
v Free elements could be any where in the Queue such as before the front, after the rear, and between front and rear in the Queue
v Queue 1s and Queue 2 s size could be change if it is necessary. When the Queue 1 is full and the Queue 2 has free space; the Queue 1 can increase the size to use that free space from the Queue 2. Same way for the Queue 2
v Elements 1, 2, and 3 are using to store the size of the Queue 1, the front of the Queue 1, and the data count for the Queue 1 needed to manipulate the Queue 1
v Elements 4, 5, and 6 are using to store the size of the Queue 2, the front of the Queue 2, and the data count for the Queue 2 needed to manipulate the Queue 2
v Inserts data to the Queue 1, Q1Rear = (Q1Front + Q1count) % Q1Size
v Inserts data to the Queue 2, Q2Rear = (Q2Front + Q2count) % Q2Size + Q1Size
v Deletes data from the Queue 1, Q1Front = (Q1Front + 1) % Q1Size
v Deletes data from the Queue 2, Q2Front = (Q2Front + 1) % Q2Size + Q1Size
v Queue 1 expands from the 0th element to the 4th element and circular back to 0th element
v Queue 2 expands from the 8th element to the 5th element and circular back to 8th element
v The boundary is fixed between the Queue 1 and the Queue 2
v Free elements could be any where in the Queue such as before the front, after the rear, and between front and rear in the Queue
v Elements 1, 2, and 3 are using to store the size of the Queue 1, the front of the Queue 1, and the data count for the Queue 1 needed to manipulate the Queue 1
v Elements 4, 5, and 6 are using to store the size of the Queue 2, the front of the Queue 2, and the data count for the Queue 2 needed to manipulate the Queue 2
v Inserts data to the Queue 1, Q1Rear = (Q1Front + Q1count) % Q1Size
v Inserts data to the Queue 2, Q2Rear = (Q2Front + Q2count) % Q2Size + Q1Size
v Deletes data from the Queue 1, Q1Front = (Q1Front + 1) % Q1Size
v Deletes data from the Queue 2, Q2Front = (Q2Front + 1) % Q2Size + Q1Size