Stacks and Queues
Contents
Stacks and Queues#
This chapter will discuss two data structures; stacks and queues. These data structures are based on arrays data structure, but unlike conventional arrays, there are restrictions on insertion, deletion, and reading items on the arrays.
Stacks and queues are dynamic arrays in which the element removed from the array by the delete operation is predetermined. In a stack, the element deletion from the array is the one most recently inserted. The stack implements a last-in, first-out, or LIFO policy. Similarly, in a queue, the element deleted is always the one that has been in the array for the longest time. The queue implements a first-in, first-out, or FIFO policy. There are several ways to implement stacks and queues on a computer. This chapter will use a simple array to implement each.
Stacks#
The stacks are implemented on arrays; however, there are a few constraints:
Elements are inserted only at the end of a stack, also called push operation
Elements are deleted only from the end of a stack, also called pop operation
Reading operation is executed from the end of a stack.
Think of a stack as a pile of plates stored, where adding and taking out plates from the pile occurs at the top of the stacks.
The insert operation on a stack is often called PUSH, and the delete operation, which does not take an element argument, is often called POP.
Programming languages don’t have stack data types but can be built using the array data type. Stack is an example of an abstract data type.
Abstract data type—it’s a kind of data structure that is a set of theoretical rules that revolve around some other built-in data structure.
Table 8 shows the number of operations can be done on a stack.
Operation |
Description |
|---|---|
push() |
adds an element to the top of the stack |
pop() |
removes an element from the top of the stack |
peek() |
returns a copy of the element on the top of the stack without removing it |
is_empty() |
checks whether a stack is empty |
is_full() |
checks whether a stack is at maximum capacity when stored in a static (fixed-size) structure |
Fig. 17 shows, we can implement a stack of at most \(n\) elements with an array \(S[1..n]\). The array has an attribute \(S.top\) that indexes the most recently inserted element. The stack consists of \(S[1..S.top]\), 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 contains no elements and is empty. We can test to see whether the stack is empty by query operations STACK-EMPTY or calling a function is_empty(). If we attempt to pop an empty stack, we say the stack underflow. If \(S.top\) exceeds \(n\), the stack overflows.
Fig. 17 An array implementation of a Stack \(S\). Stack elements appear only in the white color box positions. The green color box represents available space in an array. (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.#
The following is the pseudocode implementation of stack, without stack overflow.
1if S.top == 0
2 return TRUE
3else return FALSE
1S.top = S.top + 1
2S[S.top] = x
1if STACK-EMPTY(S)
2 error "underflow"
3else S.top = S.top-1
4 return S[S.top + 1]
The three stack operations takes \(O(1)\) time.
Queues#
In queues, we call the insert operation on a queue “enqueue”, and the delete operation “dequeue”. Similar to the POP operation in stack, 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.
The Fig. 18 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 point to, its head. The attribute \(Q.tail\) indexes the next location at which a newly arrived element will be inserted into the queue. THe elements in the queue reside in locations \(Q.head, Q.head+1...,Q.tail-1\), where we “wrap around” in the sense that location 1 immediately follows location \(n\) in a circular order. 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\) or both \(Q.head = 1\) and \(Q.tail = Q.length\), the queue is full, and if we attempt to enqueue an element, then the queue overflows.
Fig. 18 An queue implementation using an array \(Q[1..12]\). Queue elements appear only in the white color box positions. The green color box represents available space in an array. (a) THe queue has 5 elements, in location \(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.#
In our procedure ENQUEUE and DEQUEUE, we have omitted the error checking for underflow and overflow. The pseudocode assumes that \(n=Q.length\).
1Q[Q.tail] = x
2if Q.tail == Q.length
3 Q.tail = 1
4else Q.tail = Q.tail + 1
1x = Q[Q.head]
2if Q.head == Q.length
3 Q.head = 1
4else Q.head = Q.head + 1
5return x
The two queues operations takes \(O(1)\) time.
Conclusion#
Stacks are ideal for processing data in LIFO order. Applications of stacks, such as the “undo” function in a word processor and checking errors such as missing parenthesis in a code, are a few examples. Queue process requests based on FIFO order. Queues data structures are implemented on print servers, handling hardware, or real-time system interrupts are a few examples. In this chapter, only basic queues are discussed.
Bibliography#
- AMTA90
Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein. Data Structures Using C. Prentice Hall, 1 edition, 1990. ISBN 978-0131997462.
- GT15
Michael T Goodrich and Roberto Tamassia. Algorithm Design and Applications. Willey, 1 edition, 2015. ISBN 978-1118335918.
- Knu98
Donald Knuth. The Art of Computer Programming. Volume 3. Addison-Wesley Professional, 1998. ISBN 978-0-201-89685-5.
- Ope16
OpenDSA. Opendsa. 2016. URL: https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/HashDel.html.
- THCR90
Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest. Introduction to Algorithms. MIT Press, edition, 1990. ISBN.