logo
English
Data Structures

02. Stack, Queue, and Array

Stack, Queue, and Array

1. Basic Concepts of Stack and Queue

  • Stack: Last-In-First-Out (LIFO), only allows insertion and deletion at one end (the top)
  • Queue: First-In-First-Out (FIFO), insertion at one end (rear), deletion at the other (front)

2. Storage Structures

  • Sequential storage: Implemented with arrays, contiguous memory, supports random access
  • Linked storage: Implemented with linked lists, flexible memory, efficient insertion/deletion
  • Stack can be implemented sequentially or with linked lists; queue can be implemented sequentially, with linked lists, or as a circular queue

3. Storage of Multidimensional Arrays

  • Multidimensional arrays are stored linearly in memory by row-major or column-major order
  • There are formulas to calculate the address of each element

4. Compressed Storage of Special Matrices

  • Symmetric matrices, triangular matrices, sparse matrices, etc., can be compressed into one-dimensional arrays
  • This saves space and improves efficiency

5. Applications

  • Stack: Expression evaluation, recursion, parenthesis matching, function calls
  • Queue: Buffers, OS scheduling, breadth-first search in graphs
  • Array: Data storage, searching, sorting, matrix operations

Exercises

  1. Briefly describe the main differences between stacks and queues.
  2. How do you implement a circular queue using an array?
  3. How are multidimensional arrays stored in memory?
  4. Give examples of typical applications of stacks and queues.
  5. How is a sparse matrix stored in a compressed way?
Reference Answers

1. Differences between Stack and Queue

Stack: LIFO, only operates at the top;
Queue: FIFO, deletes at the front and inserts at the rear

2. Circular Queue Implementation

Use an array with front and rear pointers, use modulo to wrap around, avoiding false overflow

3. Multidimensional Array Storage

Stored linearly by row-major or column-major order, element addresses are calculated by formula

4. Typical Applications

Stack: Parenthesis matching, recursion, expression evaluation;
Queue: Buffer, scheduling, BFS

5. Sparse Matrix Compression

Only store non-zero elements and their positions, commonly using a triple table or compressed row/column storage