What is Stacks and Queues
Stacks and Queues are dynamic sets in which the element removed from the set by the DELETE operation. And an INSERT operation includes element in the set. In Stack, the element deleted from the set in an order – last in, first out, or LIFO. Similarly, in a Queue, the element deleted is always the one that has been in the set for the longest time. -which indicates the first in, first out, or FIFO policy. There are several efficient way to implement Stacks and Queues. In this article we will discuss about simple array implementation for each.
THe INSERT operation on Stack is often called PUSH. The DELETE operation, which doesn’t take an element argument, refers to as POP. These names are allusion to physical stack or pile, such as Stacks of plates in restaurant, or, Stacks of books on the shelf. The order in which plates are POPPED from the stack is the reverse of the order in which they were PUSHED onto the Stack, since only the top element is accessible.
As a stack is a list or pile of elements, therefore push or pop operation on stack is possible to perform on one element at a time. We can implement Stacks using: *Array, and *Linked lists. In this lesson, we will discuss Stacks implementation using Arrays.
Figure: An array implementation of a stack S. Stack elements appear only in the green shaded
positions. (a) Stack S has 4 elements. The top element is 9. (b) Stack S after the calls PUSH(S,17)
and PUSH(S, 3). (c) Stack S after the call POP(S) has returned the element 3, which is the one most
recently pushed. Although element 3 still appears in the array, it is no longer in the stack; the top is
Figure Above shows, we can implement a stacks of at most n elements with an Array S[1 …n]. The Array has an attribute S.top, which indexes the most recently inserted element. The Array consists of S to S[S.top] elements, where S is the element at the bottom of the Stack, and S[S.top] is the element at the top. When, S.top = 0, the stack contain no elements, and is empty. We can test whether the Stack is empty by query-operation STACK-EMPTY. If we attempt to POP an empty-Stack, we say the stack underflows, which normally an error. If S.top exceeds n, the Stack overflows. In our pseudocode implementation, we don’t worry about stack-overflow. We can implement each of the Stack-operations with just a few line of code:
if S.top == 0
else RETURN FALSE
PUSH (S, x)
S.top = S.top+1
S[S.top] = x
else S.top = S.top-1
Figure above: An array implementation of a stack S, shows the effects of the modifying operations PUSH and POP. Each of the three stack operations takes O(1) time.
We call the INSERT operation on a Queue ENQUEUE, and we call the DELETE operation DEQUEUE. Like the stack operation POP, DEQUEUE takes no element argument. The FIFO property of a queue causes it to operate like a line of customers waiting to pay a cashier. The queue has a head and a tail. When an element is enqueued, it takes its place at the tail of the queue, just as a newly arriving customer takes a place at the end of the line. The element dequeued is always the one at the head of the queue, like the customer at the head of the line who has waited the
Figure: A Queue implemented using an array Q[1..12]. Queue elements appear only in the green shaded positions. (a) The queue has 5 elements, in locations Q[7..11]. (b) The configuration of the queue after the calls ENQUEUE(Q, 17), ENQUEUE(Q, 3), and ENQUEUE(Q, 5). (c) The configuration of the queue after the call DEQUEUE(Q) returns the key value 15 formerly at the head of the queue. The new head has key 6.
Figure above, shows one way to implement a queue of at most n-1 elements using an array Q[1..n]. The queue has an attribute Q.head that indexes, or points to, its head. The attribute Q.tail indexes the next location at which a newly arriving element will be inserted into the queue. The elements in the queue reside in locations Q.head, Q.head+1, …, Q.tail-1. When Q.head = Q.tail, the queue is empty. Initially, we have Q.head = Q.tail = 1. If we attempt to dequeue an element from an empty queue, the queue underflows. When Q.head = Q.tail +1, the queue is full, and if we attempt to enqueue an element, then the queue overflows. The pseudocode for queue assumes that n=Q.length.
Q[q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail+1
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head+1
Figure Above: QUEUE Implementation shows the effects of ENQUEUE and DEQUEUE operation. Each operation takes O(1) time. we will discuss about big ″O″ in Algorithm Section ».
Implementation of STACKS and QUEUES in JAVA.
This is the end of discussion on Data Structure: Stacks and Queues, This article taken from the book: Introduction to Algorithm – by Thomas H. Cormen.