Master Python Stack and Queue: Build Your Own Data Structures

Stack is a last‑in‑first‑out (LIFO) data structure, analogous to cars entering a dead‑end lane where the first car in is the last to leave.

We can define a Stack class that stores elements in a list and uses list.append() for push and list.pop() for pop. The class includes methods push, pop, isfull, and isempty.

class Stack():
    def __init__(self, size):
        self.size = size
        self.stack = []
        self.top = -1

    def push(self, ele):
        # check if full
        if self.isfull():
            raise Exception("out of range")
        else:
            self.stack.append(ele)
            self.top = self.top + 1

    def pop(self):
        # check if empty
        if self.isempty():
            raise Exception("stack is empty")
        else:
            self.top = self.top - 1
            return self.stack.pop()

    def isfull(self):
        return self.top + 1 == self.size

    def isempty(self):
        return self.top == -1

Example usage in stacktest.py:

#!/usr/bin/python
from stack import Stack
s = Stack(20)
for i in range(3):
    s.push(i)
s.pop()
print s.isempty()

Queue is a first‑in‑first‑out (FIFO) data structure, similar to customers lining up at a checkout.

We can define a Queue class that uses a list, with list.append() for enqueue and list.pop(0) for dequeue. The class provides enqueue, dequeue, isfull, and isempty methods.

class Queue():
    def __init__(self, size):
        self.size = size
        self.front = -1
        self.rear = -1
        self.queue = []

    def enqueue(self, ele):  # 入队操作
        if self.isfull():
            raise Exception("queue is full")
        else:
            self.queue.append(ele)
            self.rear = self.rear + 1

    def dequeue(self):
        # 出队操作
        if self.isempty():
            raise Exception("queue is empty")
        else:
            self.front = self.front + 1
            return self.queue[self.front]

    def isfull(self):
        return self.rear - self.front + 1 == self.size

    def isempty(self):
        return self.front == self.rear

q = Queue(10)
for i in range(3):
    q.enqueue(i)
print q.dequeue()
print q.isempty()