队列-栈基本原理

labuladong原创约 1150 字

We've covered the two main storage methods in computers: sequential storage (arrays) and linked storage (linked lists). All subsequent data structures we'll discuss are based on these two methods, with some creative twists.

This article will explain the basic principles of queues and stacks. Subsequent articles will delve into how to implement them in code.

Let's start with the concepts. Both queues and stacks are data structures with "restricted operations." By restricted, I mean that compared to the basic array and linked list, the APIs they provide are not complete.

For example, with the arrays and linked lists we've implemented, we've covered APIs for adding, deleting, checking, and modifying elements. You can add, delete, check, or modify elements at any index, as long as the index is within bounds.

However, with queues and stacks, the operations are limited: A queue can only insert elements at one end and remove them from the other; a stack can only insert and remove elements from one end.

To put it vividly, a queue allows insertion at the rear and deletion at the front, while a stack allows insertion and deletion only at the top:

A queue is like waiting in line to buy tickets; the first to come are the first to buy, and the last to come are the last to buy. A stack is like a stack of plates, with the first plate placed at the bottom and the last plate left on top, and the top plate is always taken first when removing. That's why we often say that a queue is a "first in, first out" data structure, while a stack is a "first in, last out" data structure.

Of course, the stack is drawn vertically and the queue horizontally in this diagram just to make it more intuitive. But in reality, both are implemented using arrays and linked lists, which we will discuss later.

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

java 🟢

// 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();
}

cpp 🤖

// 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;
};

python 🤖

# 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

go 🤖

// 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 {}

javascript 🤖

// 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.