In the fundamental data structure, besides the linked list, the stack and queue are also used widely in computer science and programming.

Table of content

• What is a stack data structure?
• What is a queue data structure?
• The difference between stack and queue
• How to implement in Python
• Stack
• Queue
• Conclusion

What is a stack data structure?

A stack is a way to manage data and the data order based on the (LIFO) Last In, First Out principle.

What is a queue data structure?

A stack is a way to manage data and the data order based on the (FIFO) First In, First Out principle.

The difference between stack and queue

Both stack and queue are abstract data types that are used in computer science and programming.

Some key differences are below:

Operations:

• Stack:
• Push: Add an element to the top of the stack
• Pop: Removes and returns the top element from the stack
• Is Empty: Check stack is empty
• Peek: Return the top element from the stack
• Queue:
• Push: Add an element to the end of the queue
• Pop: Removes and returns the first element from the queue
• Is Empty: Check queue is empty
• Peek: Return the first element from the queue

Usage:

• Stack: Used for tasks (managing function calls in a program, undoing functionality in applications, and parsing expressions)
• Queue: Used for scenarios (managing tasks in a printer spooler, managing requests in a web server, and implementing breadth-first search algorithms)

Implementation: The queue is implemented more complex than the stack

Order of Operations:

• Stack: LIFO - the element that was added last is the one to be removed first
• Queue: FIFO - the element that was added first is the one to be removed first

How to implement in Python

You can clone the source code stack and queue to follow it more easily.

class Node:
  def __init__(self, data: int) -> None:
    self.data = data
    self.next = None

Stack

• Create a class Stack

class Stack:
  def __init__(self) -> None:
    self.head = None

• Check is empty func

def is_empty(self):
  if self.head == None:
    return True
  else:
    return False

• Add an element

def push(self,data):
  new_node = Node(data)

  if self.head == None:
    self.head = new_node
    return

    new_node.next = self.head
    self.head = new_node

• Remove an element

def pop(self):
  if self.is_empty():
    return None

  popped_node = self.head
  self.head = self.head.next
  popped_node.next = None

  return popped_node.data

• Return an element

def peek(self):
  if self.is_empty():
    return None

  return self.head.data

Queue

• Create a class Queue

class Queue:
  def __init__(self) -> None:
    self.head = None

• Check is empty func

def is_empty(self):
  if self.head == None:
    return True
  else:
    return False

• Add an element

def push(self,data):
  new_node = Node(data)

  if self.head == None:
    self.head = new_node
    return
    
  current = self.head

  while current.next:
    current = current.next
  current.next = new_node

• Remove an element

def pop(self):
  if self.is_empty():
    return None

  popped_node = self.head
  self.head = self.head.next
  popped_node.next = None

  return popped_node.data

• Return an element

def peek(self):
  if self.is_empty():
    return None

  return self.head.data

Conclusion

In summary, understanding the differences between stacks and queues is essential for choosing the appropriate data structure for specific problem-solving scenarios in computer science and programming.