Queue/Stack Basic

The two types of storage in computers, sequential storage (arrays) and linked storage (linked lists), have been covered. All subsequent data structures are essentially extensions of these two storage methods.

This article explains the basic principles of queues and stacks. Future articles will detail how to implement them in code.

Let's start with the concepts. Both queues and stacks are data structures with "restricted operations." This means, compared to basic arrays and linked lists, the APIs they provide are not complete.

For example, with the arrays and linked lists we discussed earlier, you could perform insertions, deletions, searches, and updates on any index, as long as the index was within bounds.

However, the operations for queues and stacks are limited: A queue allows insertion at one end and deletion at the other, while a stack allows both insertion and deletion at one end only.

In simple terms, a queue allows elements to be added at the back and removed from the front, while a stack allows elements to be added and removed from the top:

A queue is like standing in line to buy tickets; those who arrive first buy first, and those who arrive later buy later. A stack is like a stack of plates; the first plate placed is at the bottom, and the last one placed is on top, with the topmost plate being removed first. This is why we say a queue is a "first in, first out" data structure, while a stack is a "last in, first out" data structure.

Of course, in the illustration, the stack is drawn vertically and the queue horizontally for better visualization. In reality, both are implemented using arrays and linked lists, which will be explained later.

The basic APIs for these two data structures are as follows:

// Basic API of the queue
class MyQueue<E> {
    // Insert an element at the end of the queue, time complexity O(1)
    void push(E e);

    // Remove an element from the front of the queue, time complexity O(1)
    E pop();

    // View the element at the front of the queue, time complexity O(1)
    E peek();

    // Return the number of elements in the queue, time complexity O(1)
    int size();
}

// Basic API of the stack
class MyStack<E> {
    // Insert an element at the top of the stack, time complexity O(1)
    void push(E e);

    // Remove an element from the top of the stack, time complexity O(1)
    E pop();

    // View the element at the top of the stack, time complexity O(1)
    E peek();

    // Return the number of elements in the stack, time complexity O(1)
    int size();
}

// Basic API of the queue
template <typename E>
class MyQueue {
public:
    // Insert an element at the end of the queue, time complexity O(1)
    void push(const E& e);

    // Remove an element from the front of the queue, time complexity O(1)
    E pop();

    // View the element at the front of the queue, time complexity O(1)
    E peek() const;

    // Return the number of elements in the queue, time complexity O(1)
    int size() const;
};

// Basic API of the stack
template <typename E>
class MyStack {
public:
    // Insert an element at the top of the stack, time complexity O(1)
    void push(const E& e);

    // Remove an element from the top of the stack, time complexity O(1)
    E pop();

    // View the element at the top of the stack, time complexity O(1)
    E peek() const;

    // Return the number of elements in the stack, time complexity O(1)
    int size() const;
};

# Basic API of the queue
class MyQueue:

    # Insert an element at the end of the queue, time complexity O(1)
    def push(self, e):
        pass

    # Delete an element from the front of the queue, time complexity O(1)
    def pop(self):
        pass

    # View the element at the front of the queue, time complexity O(1)
    def peek(self):
        pass

    # Return the number of elements in the queue, time complexity O(1)
    def size(self):
        pass

# Basic API of the stack
class MyStack:
    
    # Insert an element at the top of the stack, time complexity O(1)
    def push(self, e):
        pass
    
    # Delete an element from the top of the stack, time complexity O(1)
    def pop(self):
        pass
    
    # View the element at the top of the stack, time complexity O(1)
    def peek(self):
        pass
    
    # Return the number of elements in the stack, time complexity O(1)
    def size(self):
        pass

// Basic API of the queue
type MyQueue[T any] struct {
}

// Insert element at the end of the queue, time complexity O(1)
func (q *MyQueue[T]) Push(e T) {}

// Delete element from the front of the queue, time complexity O(1)
func (q *MyQueue[T]) Pop() T {}

// View the element at the front of the queue, time complexity O(1)
func (q *MyQueue[T]) Peek() T {}

// Return the number of elements in the queue, time complexity O(1)
func (q *MyQueue[T]) Size() int {}

// Basic API of the stack
type MyStack[T any] struct {
}

// Insert element at the top of the stack, time complexity O(1)
func (s *MyStack[T]) Push(e T) {}

// Delete element from the top of the stack, time complexity O(1)
func (s *MyStack[T]) Pop() T {}

// View the element at the top of the stack, time complexity O(1)
func (s *MyStack[T]) Peek() T {}

// Return the number of elements in the stack, time complexity O(1)
func (s *MyStack[T]) Size() int {}

// Basic API of the queue
class MyQueue {
    // Insert element at the end of the queue, time complexity O(1)
    push(e) {}

    // Delete element from the front of the queue, time complexity O(1)
    pop() {}

    // View the element at the front of the queue, time complexity O(1)
    peek() {}

    // Return the number of elements in the queue, time complexity O(1)
    size() {}
}

class MyStack {
    // Insert element at the top of the stack, time complexity O(1)
    push(e) {}

    // Delete element from the top of the stack, time complexity O(1)
    pop() {}

    // View the element at the top of the stack, time complexity O(1)
    peek() {}

    // Return the number of elements in the stack, time complexity O(1)
    size() {}
}

In different programming languages, the names of the methods provided by queues and stacks may vary, but the effect of each method is definitely the same.

Some languages' standard libraries may not directly provide queues and stacks, but you can simulate the effects of queues and stacks using arrays or linked lists on your own. In the next chapter, I will guide you through implementing queues and stacks using linked lists first.