Stacks and Queues
Explore the fundamentals of stacks and queues, focusing on their first-in-last-out and first-in-first-out behaviors. Understand how these data structures are implemented using arrays or linked lists, compare their operation complexities, and consider memory trade-offs to choose the best implementation for your coding needs.
We'll cover the following...
Stack
Stack is a well-known data-structure, which follows first in, last out paradigm. It offers push and pop operations. We'll examine the complexity of these operations when stack is implemented using an array or a linked list.
Stack using Linked List
A stack can be implemented using a linked list. New items are always appended and removed at the head of the list. We discussed in the linked list section that appending an item to the head of a linked list takes constant time. Therefore, both push and pop operations take constant or O(1) time.
However, note that when we use a linked list we are still using an extra pointer in each node of the list to keep track of the next node in the chain. That additional cost allows us to ...