Stacks and Queues
This lesson talks about operations on stacks and queues.
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 ...