DSA Day-20

Hey Guys!!!

It’s Day-20 in this series of 30 Days DSA, we’ll be moving to the most important topics now on: Stacks, Queues, Trees, Graphs. A lot of questions can be asked from these topics.Use of all these data structures reduces the time complexity and are very useful in solving problems.

Today, we’ll be learning about stacks and queues.

STACKS

The Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

  • The LIFO order says that the element which is inserted at the last in the Stack will be the first one to be removed. In LIFO order insertion takes place at the rear end of the stack and deletion occurs at the front of the stack.
  • The FILO order says that the element which is inserted at the first in the Stack will be the last one to be removed. In FILO order insertion takes place at the rear end of the stack and deletion occurs at the front of the stack.

Mainly the following three basic operations are performed in the stack:

  • Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
  • Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
  • Peek or Top: Returns top element of stack.
  • isEmpty: Returns true if stack is empty, else false.

Time Complexities of operations on stack: The operations push(), pop(), isEmpty() and peek() all take O(1) time.

Implementation: There are two ways to implement a stack.

  • Using array
  • Using linked list

You can refer to the following link for these implementation, it’ll prove to be really helpful and questions related to it can be asked in interviews.

Important Problems on implementation of stacks:

  1. Infix to Postfix Conversion**
  2. Valid Parentheses**
  3. Implementing two stacks using one array
  4. Implementing stacks using arrays
  5. Implementing stacks using Linked List

(**: Very important/ Must- do)

QUEUE

Like Stack data structure, Queue is also a linear data structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO) which means that the element which is inserted first in the queue will be the first one to be removed from the queue. A good example of queue is any queue of consumers for a resource where the consumer that came first is served first.

The difference between stacks and queues is in removing. In a stack we remove the most recently added item; in a queue, we remove the least recently added item.

Operations on Queue: Mainly the following four basic operations are performed on queue:

  • Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
  • Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
  • Front: Get the front item from queue.
  • Rear: Get the last item from queue.

Above two links should be referred for understanding the implementation of arrays.

Other very important problem under stacks and queues is:

  1. Implementation of stack using queues**

https://www.geeksforgeeks.org/implement-stack-using-queue/

2. Implementation of queues using stacks **

The problems introduced in this segment of stacks and queues is extremely important and has to be on your finger tip before you sit for placements.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Arya Goswami

Arya Goswami

Incoming SDE intern at Amazon || Ex- mentee at Amazon ACMS