Implementing Stacks and Queues

In this section, we will cover the implementation of stacks and queues in code. We will set up the necessary boilerplate for both data structures and then implement the core operations.

Implementing a Stack

A stack can be implemented using a list or an array. For our implementation, we will use a Python list.

1# Python code here
2
3class Stack:
4    def __init__(self):
5        self.items = []
6
7    def push(self, item):
8        self.items.append(item)
9
10    def pop(self):
11        if not self.is_empty():
12            return self.items.pop()
13
14    def peek(self):
15        if not self.is_empty():
16            return self.items[-1]
17
18    def is_empty(self):
19        return len(self.items) == 0
20
21    def size(self):
22        return len(self.items)

Let's break down the implementation:

• The __init__ method initializes an empty list to store the elements of the stack.
• The push method appends an item to the top of the stack.
• The pop method removes and returns the topmost item from the stack if the stack is not empty.
• The peek method returns the topmost item from the stack without removing it if the stack is not empty.
• The is_empty method checks if the stack is empty by examining the length of the items list.
• The size method returns the number of items in the stack by returning the length of the items list.

Implementing a Queue

Similar to a stack, a queue can also be implemented using a list or an array. For our implementation, we will use a Python list.

1# Python code here
2
3class Queue:
4    def __init__(self):
5        self.items = []
6
7    def enqueue(self, item):
8        self.items.insert(0, item)
9
10    def dequeue(self):
11        if not self.is_empty():
12            return self.items.pop()
13
14    def is_empty(self):
15        return len(self.items) == 0
16
17    def size(self):
18        return len(self.items)

Let's break down the implementation:

• The __init__ method initializes an empty list to store the elements of the queue.
• The enqueue method inserts an item at the front of the queue.
• The dequeue method removes and returns the rearmost item from the queue if the queue is not empty.
• The is_empty method checks if the queue is empty by examining the length of the items list.
• The size method returns the number of items in the queue by returning the length of the items list.

Now that we have implemented the stack and queue data structures, we can move on to exploring their operations in the next sections.

xxxxxxxxxx

    main()

def main():

    class Stack:

        def __init__(self):

            self.items = []

​

        def push(self, item):

            self.items.append(item)

​

        def pop(self):

            if not self.is_empty():

                return self.items.pop()

​

        def peek(self):

            if not self.is_empty():

                return self.items[-1]

​

        def is_empty(self):

            return len(self.items) == 0

​

        def size(self):

            return len(self.items)

​

    class Queue:

        def __init__(self):

            self.items = []

​

        def enqueue(self, item):

            self.items.insert(0, item)

​