Ryoma Taniyama

close up photo of bamboo steamers

Stacks and Queues

Stacks

What Is Stack?

A stack is a data structure in which we can only access the element that was added last, and this access follows last-in-first-out (LIFO) principle. Stacks, for instance, can be used to implement a redo and undo function, and a backtracking algorithm (such as depth-first search, DFS).

Implementations

Stacks typically support the following operations.

  • pop: Remove the top element, which is the last element added.
  • push: Add an element to the top of the stack.
  • peek: Return the top of the stack.

There are two common ways to implement a stack; using a linked list, and using an array.

In an implementation using a linked list, we can consider the head of the linked list as the top of the stack. Since inserting and removing an element at the beginning of a linked list takes constant time, the time complexity of the operations over stacks is also constant, \(O(1)\).

What about using an array? The time complexity depends on its implementation. If the beginning of an array represents the top of the stack, in order to push new element, we have to shift all the existing elements in the array, which would take \(O(n)\). On the other hand, if the end of the array is the top, a push operation doesn’t involve any shifting, though. Consequently, its time complexity is constant, \(O(1)\).

Queues

What Is Queue?

A queue is a data structure in which we can only retrieve its elements in the same order that they are added, which follows first-in-first-out (FIFO) principle. Queues are commonly used to implement a cache, and a breadth-first search.

Implementations

Queues typically support the following operations:

  • dequeue: Remove the top element, which is the oldest element.
  • enqueue: Add a new element at the end of the queue.
  • peek: Return the top of the queue.

Queues can also be implemented using either an array or a linked list. When using a singly linked list with a tail pointer, and considering the head of the linked list as the top of the stack, the time complexity of each operation is \(O(1)\).

Reference

Posted

in

Tags: