Programming Data Structure Stacks and Queues - Data Structure

Stacks and Queues – Data Structure

-

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.

STACKS


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.

Stacks and Queues - Data Structure - CS School

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
element 17.

Stack Implementation


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[1] to S[S.top] elements, where S[1] 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:

STACK-EMPTY(S)
if S.top == 0
return TRUE
else RETURN FALSE

PUSH (S, x)
S.top = S.top+1
S[S.top] = x

POP(S)
if STACK_EMPTY(S)
error “underflow”
else S.top = S.top-1
return S[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.

QUEUES


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
longest.

Stacks and Queues - Stack Implementation - CS school

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.

Queue Implementation


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.

ENQUEUE(Q, x)
Q[q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail+1

DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head+1
return x

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.

Latest Articles

Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you