CampusLearn
← CSC 212 Data Structures and Algorithms

Linear Data Structures: Stacks and Queues in Systems Architecture

Notes

Overview of Stacks and Queues Linear data structures organize elements sequentially, where each element has a unique predecessor and successor, except for the first and last elements. Stacks and queues represent constrained linear structures governed by specific access disciplines. A stack operates on a Last-In, First-Out (LIFO) model, meaning the most recently inserted element is the first one removed. In contrast, a queue operates on a First-In, First-Out (FIFO) discipline, ensuring fairness where elements are serviced in the exact order of their arrival. Abstract Data Type Operations and Complexity A stack Abstract Data Type (ADT) primarily exposes push to add an element to the top, pop to remove and return the top element, and peek to view the top element without removal. When implemented via dynamic arrays or linked lists, these fundamental stack operations achieve O(1) constant time complexity. A standard queue ADT provides enqueue to append an item to the rear and dequeue to extract an item from the front. A naive array implementation of a queue causes O(n) shift overhead upon dequeue; therefore, circular arrays or doubly linked lists are adopted to maintain O(1) efficiency for both insertion and deletion operations. Memory Allocation and Hardware Integration Stacks are directly mirrored in execution hardware via the call stack, maintaining activation records, local variables, and return pointers for subroutines. Queues underpin asynchronous systems, acting as buffers that decouple high-throughput producers from slower consumers, preventing buffer overflows and system lockups. Practical example Consider the architectural design of Safaricom's M-Pesa USSD service (*334#). When a customer navigates through interactive nested menus (such as Send Money, followed by Enter Phone Number, followed by Amount), the mobile telecommunication gateway utilizes a stack structure to track session state. Each selected menu screen is pushed onto the session stack. If the customer inputs '0' or 'Back', the system executes a pop operation, instantly unwinding the state to restore the previous screen context in O(1) time. Simultaneously, completed money transfers enter a transaction processing queue managed by an enterprise message broker. When thousands of subscribers across Nairobi, Mombasa, and Kisumu hit send during evening peak hours, their transactions are enqueued sequentially into a FIFO buffer. Backend settlement engines dequeue each transaction sequentially, ensuring that user A who submitted a transfer at 17:00:01 is processed before user B who submitted at 17:00:02, thereby preserving financial audit integrity and preventing race conditions across core banking ledgers.

Quiz

1. Which access discipline governs the processing order of an operating system print spooler or an asynchronous SMS gateway buffer?

2. What is the primary operational consequence of implementing a basic queue using a linear non-circular array without shifting pointers?

3. In the M-Pesa USSD session example, why is a stack preferred over a queue for tracking screen navigation?

Sign in to submit and securely grade your quiz.