Python Stack & Queue

Introduction

In computer science, a stack and a queue are two of the basic data structures. Both are used to store and access data in an organized way.

A stack is a data structure that follows the Last In First Out (LIFO) principle. It means that the last item inserted into the stack will be the first one to be removed.

A queue, on the other hand, is a data structure that follows the First In First Out (FIFO) principle. It means that the first item inserted into the queue will be the first one to be removed.

Syntax

Stack

To create a stack in Python, we use a list. Here are some commonly used methods of the list that can be used to implement a stack:

• append(item) - adds item to the top of the stack.

• pop() - removes and returns the item at the top of the stack.

• peek() - returns the item at the top of the stack without removing it.

Here is the syntax to create and use a stack:

stack = []
stack.append(item)
stack.pop()
stack.peek()

Queue

Similarly, to create a queue in Python, we can also use a list. Here are some commonly used methods of the list that can be used to implement a queue:

• append(item) - adds item to the back of the queue.

• pop(0) - removes and returns the item at the front of the queue.

• peek() - returns the item at the front of the queue without removing it.

Here is the syntax to create and use a queue:

queue = []
queue.append(item)
queue.pop(0)
queue.peek()

Example

Stack

Consider the following example of a stack:

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

print(stack.pop())   # Output: 3
print(stack.pop())   # Output: 2
print(stack.pop())   # Output: 1

Queue

Consider the following example of a queue:

queue = []

queue.append(1)
queue.append(2)
queue.append(3)

print(queue.pop(0))   # Output: 1
print(queue.pop(0))   # Output: 2
print(queue.pop(0))   # Output: 3

Output

The output of the above examples will be:

3
2
1

and

1
2
3

Explanation

In the stack example, we first create an empty stack using stack = []. Then we push three elements to the top of the stack using the append() method. Finally, we retrieve and remove each element using the pop() method in reverse order. Since the LIFO principle is followed, the last element pushed is the first to be popped.

In the queue example, we first create an empty queue using queue = []. Then we add three elements to the back of the queue using the append() method. Finally, we retrieve and remove each element using the pop(0) method in order. Since the FIFO principle is followed, the first element added is the first to be popped.

Use

Stack and queue are used in many algorithms. Some common uses for stacks are:

• Evaluating expressions: Stacks can be used to evaluate expressions such as arithmetic expressions, boolean expressions, and more.

• Reversing series: Stacks can be used to reverse a string or a series of numbers.

• Parenthesis Matching: One of the most common uses of a stack is to matching parenthesis. It is used to check whether the opening and closing parentheses are properly matched in a string.

Some common uses for queues are:

• BFS: A basic usage of the queue is to traverse a graph in BFS (Breadth-First Search) algorithm.

• Job scheduling: In computer science, queues are used for processing jobs, where jobs are added to the queue and then processed one-by-one.

• Resource Sharing: Queues are used to share resources between different processes, which can access the resources through the queue.

Important Points

• Stacks follow the LIFO (Last In First Out) principle, while Queues follow the FIFO (First In First Out) principle.

• In Python, both can be implemented using the built-in list data type.

• Stacks and Queues are fundamental data structures, and they form the basis of many complex data structures and algorithms.

Summary

Stack and queue are two of the fundamental data structures used in computer science. They are used to store and access data in an organized way. A stack follows the Last In First Out (LIFO) principle, whereas a queue follows the First In First Out (FIFO) principle. In Python, both can be implemented using the built-in list data type. They are used in many algorithms and can be used for evaluating expressions, reversing series, BFS, job scheduling, and resource sharing.