Stacks and Queues

Uncategorized
Wishlist Share
Share Course
Page Link
Share On Social Media

About Course

Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. It can be visualized as a pile of plates where you can only add or remove the top plate.

Operations on Stack:

The primary operations associated with a stack are:

  • Push: Adds an element to the top of the stack.
  • Pop: Removes and returns the top element of the stack.
  • Peek (or Top): Returns the top element of the stack without removing it.
  • IsEmpty: Checks if the stack is empty.
  • Size: Returns the number of elements in the stack.

Use Cases of Stack:

Stacks are used in various applications, including:

  • Function Call Management: The call stack in programming languages keeps track of function calls and returns.
  • Expression Evaluation: Used in parsing expressions and evaluating postfix or prefix notations.
  • Backtracking: Helps in algorithms that require exploring all possibilities, such as maze solving and depth-first search.

Queues

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed. It can be visualized as a line of people waiting for a service, where the first person in line is the first to be served.

Operations on Queue:

The primary operations associated with a queue are:

  • Enqueue: Adds an element to the end (rear) of the queue.
  • Dequeue: Removes and returns the front element of the queue.
  • Front (or Peek): Returns the front element of the queue without removing it.
  • IsEmpty: Checks if the queue is empty.
  • Size: Returns the number of elements in the queue.

Use Cases of Queue:

Queues are used in various applications, including:

  • Task Scheduling: Operating systems use queues to manage tasks and processes.
  • Breadth-First Search (BFS): In graph traversal algorithms, queues help in exploring nodes level by level.
  • Buffering: Used in situations where data is transferred asynchronously, such as IO buffers and print spooling.

Key Differences Between Stack and Queue

Here is a table that highlights the key differences between stack and queue data structures:

Feature Stack Queue
Definition A linear data structure that follows the Last In First Out (LIFO) principle. A linear data structure that follows the First In First Out (FIFO) principle.
Primary Operations Push (add an item), Pop (remove an item), Peek (view the top item) Enqueue (add an item), Dequeue (remove an item), Front (view the first item), Rear (view the last item)
Insertion/Removal Elements are added and removed from the same end (the top). Elements are added at the rear and removed from the front.
Use Cases Function call management (call stack), expression evaluation and syntax parsing, undo mechanisms in text editors. Scheduling processes in operating systems, managing requests in a printer queue, breadth-first search in graphs.
Examples Browser history (back button), reversing a word. Customer service lines, CPU task scheduling.
Real-World Analogy A stack of plates: you add and remove plates from the top. A queue at a ticket counter: the first person in line is the first to be served.
Complexity (Amortized) Push: O(1), Pop: O(1), Peek: O(1) Enqueue: O(1), Dequeue: O(1), Front: O(1), Rear: O(1)
Memory Structure Typically uses a contiguous block of memory or linked list. Typically uses a circular buffer or linked list.
Implementation Can be implemented using arrays or linked lists. Can be implemented using arrays, linked lists, or circular buffers.

 

Deques

Deque also known as double ended queue, as name suggests is a special kind of queue in which insertions and deletions can be done at the last as well as at the beginning.

A link-list representation of deque is such that each node points to the next node as well as the previous node. So that insertion and deletions take constant time at both the beginning and the last.

Now, deque can be used to implement a stack and queue. One simply needs to understand how deque can be made to work as a stack or a queue.

The functions of deque to tweak them to work as stack and queue are listed below.

Time Complexity: O(n)
Auxiliary Space: O(n)

Implement queues using two stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.
  • int pop() Removes the element from the front of the queue and returns it.
  • int peek() Returns the element at the front of the queue.
  • boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

 

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to push, pop, peek, and empty.
  • All the calls to pop and peek are valid.

 

Show More

Student Ratings & Reviews

No Review Yet
No Review Yet