In this post, I present the concepts of stack and queue which are fundamental in computer science. Furthermore, I demonstrate them with an interactive application below to clearly and visually present what goes on as new elements are added or removed from each and their differences in behavior.
The implementation of a stack and queue is also discussed.
First, let’s understand what they are.
Stack: A stack is a data structure that follows the Last In, First Out (LIFO) principle. Example: A stack of plates; where you add to or remove the top plate. The last item added is the first one to be removed. Common operations: push (add an item), pop (remove the top item).
Queue: A queue is a data structure that follows the First In, First Out (FIFO) principle. Example: People waiting in line to buy a movie ticket; the first person in line is the first to be served. Common operations: enqueue (add an item to the end) and dequeue (remove the item from the front).
They are both used in various applications, such as task scheduling and managing resources.
The Demo Application:
The application has command buttons to create a stack, queue, add elements to each independently: Push (Stack) and Push (Queue), and remove elements (pop) from each independently: Pop (Stack), Pop (Queue). Clicking the Create A Stack creates a stack of 5 elements. Clicking the Create A Queue creates a queue of 5 elements. I’m using letters or strings for stack and numbers for queues, but they can be any other data type or of a mix of data types in each data structure. As new elements are added to either or removed from either, the respective contents are shown in the window. The window can be resized by user anytime, but it will automatically change its size depending on the size of the stack or queue in real-time. After pushing the Create A Stack and Create A Queue buttons, the window looks something like this:
My script adds the elements from a collection of letters and numbers in random order for the stack and queue respectively each time Create or Push commands are issued.
You can try it yourself below. Click on Run on the widget and see what happens, then compare with their concepts described above.
As you click Push (Stack) or Pop (Stack) buttons, pay attention to the Stack content shown on the top right. Similarly, As you click Push (Queue) or Pop (Queue) buttons, pay attention to the Queue content shown on the bottom right side. You’ll notice the differences in behavior exactly as they’re supposed to perform; that is, Stack adds and removes from the topmost or rightmost position of the content, whereas Queue adds to the rightmost but removes from the leftmost position.
Implementation:
Both stack and queue in this code are implemented here as list objects. Both use list.append() function is used to perform the push functions…to add a new element to the end (rightmost position) of the lists (stack or queue). The push functionality is the same for both stacks and queues. What differs is what’s removed first. For queues, we call the add operation enqueue.
Pop functionality is achieved by using Python’s pop() function. pop() removes the rightmost item, so it works as-is for stacks (where the last or rightmost item is the topmost item).
However, for Queue’s we specify the index 0 as: pop(0) because in queue we always remove the first item from the queue list. For queues, we call the removal operation dequeue (not to be confused with ‘deque’).
We could also use popleft() function instead of pop(0) for queues but we’d have to use the ‘deque’ class from the ‘collections’ module as the standard Python library does not have popleft(). The ‘deque’ class, double-ended queue, is optimized for fast appends and pops from both ends (first or last).
The entire script is object-oriented, so both the stack and the queue are objects with their own methods and properties. They don’t have to be, but that’s a better design for this purpose.
The Demo Code:
The required libraries and modules are imported. Because I randomly select the elements to add into the stack or queue, random library is required. tkinter is required for the GUI.
import tkinter as tk
import random
The last part is the standard tkinter lines to create the gui object, and of course, create our app object based on the StackQueueApp class (described below):
if name == "main":
root = tk.Tk()
app = StackQueueApp(root)
root.mainloop()
The class is defined as follows along with the methods required for all operations:
As you can see both stacks and queues are implemented as simple lists here.
The code for each of these methods are filled in next. create_widgets() is responsible for creating the UI elements, and update_labels() takes care of displaying stack and queue labels and content in the UI. create_stack() populates the initial stack composed of letters. create_queue() populates the initial queue composed of numbers. push_stack() uses list.append() to add a new element (randomly chosen from the letters list) to the stack variable which is a list object. The pop_stack() uses Python’s built-in pop() function to remove the topmost (last) element, if any, from the current stack.
Similarly, the queue methods are defined as:
As mentioned earlier, you can always use ‘deque’ class instead of a list for our Queue object, and use popleft() method instead of pop(0). To use ‘deque’ class instead of a list for our Queue object, make the following changes to the script:
First, from collections import deque
In pop_queue() function, use self.queue.popleft() instead of self.queue.pop(0)
Then create the queue object called ‘queue’ with this instantiation: self.queue = deque() instead of self.queue = []
In create_queue() function, use this: self.queue = deque(random.sample(['A', 'B', 'C', 'D', 'E'], 5)) instead of self.queue = random.sample([…], 5)
Everything else remains the same. As for the tkinter part of the code, I’m using grid system to align the widgets neatly and also to enable auto-resizing of the window as the widgets grow or shrink.
The application script presented is a good educational tool for several reasons:
Concept Demonstration: It visually demonstrates the fundamental concepts of stacks and queues. Interactive Learning: The interactive nature of the GUI allows users to see the immediate effects of stack and queue operations, thereby able to easily relate to the concepts.
And as a bonus, understanding Tkinter: It introduces the tkinter library, which is a standard way to create GUIs in Python.
I hope this was educational and interesting. You can get the full source code from my Patreon shop here (secure transaction).
In a future post, I plan to post additional applications of stack and queue using tkinter for practical, educational purposes such as path navigation, board games, etc.
