C++队列与栈：两种经典数据结构的实现和应用 |21xrx.com

C++队列与栈：两种经典数据结构的实现和应用

2023-07-06 10:14:53 深夜i -- --

C++ 队列栈数据结构应用

C++是一种强大的编程语言，可以用来实现各种数据结构。队列和栈是两种经典的数据结构，它们可以用来解决很多实际问题。在本文中，我们将介绍C++如何实现队列和栈，以及它们的应用。

1. 队列

队列是一种先进先出（FIFO）的数据结构。一个队列有两个端点，一个是“front”端，一个是“rear”端。元素从rear端入队，从front端出队。队列可以用数组或链表实现。

C++数组实现：


class Queue{
private:
  int arr[SIZE];
  int rear, front;
public:
  Queue()
    rear = -1;
    front = 0;
  
  void enqueue(int x){
    if(rear == SIZE - 1)
      cout << "Queue is full" << endl;
      return;
    
    arr[++rear] = x;
  }
  void dequeue(){
    if(front > rear)
      cout << "Queue is empty" << endl;
      return;
    
    cout << "Element dequeued from queue is: " << arr[front++] << endl;
  }
}

C++链表实现：


class Node{
public:
  int data;
  Node* next;
};
class Queue{
private:
  Node* front;
  Node* rear;
public:
  Queue()
    front = NULL;
    rear = NULL;
  
  void enqueue(int x){
    Node* temp = new Node();
    temp->data = x;
    temp->next = NULL;
    if(front == NULL && rear == NULL)
      front = rear = temp;
      return;
    
    rear->next = temp;
    rear = temp;
  }
  void dequeue(){
    Node* temp = front;
    if(front == NULL)
      cout << "Queue is empty" << endl;
      return;
    
    if(front == rear)
      front = rear = NULL;
    
    else
      front = front->next;
    
    delete temp;
  }
}

队列的应用：

- 操作系统中进程的调度

- 雷达系统中的请求处理

- 扫描大量数据时的缓存

2. 栈

栈是一种后进先出（LIFO）的数据结构。栈有两个基本操作：push（入栈）和pop（出栈）。除了这两个操作，栈还有一个非常重要的操作——peek，用于获取栈顶元素。栈可以用数组或链表实现。

C++数组实现：


class Stack{
private:
  int arr[SIZE];
  int top;
public:
  Stack()
    top = -1;
  
  void push(int x){
    if(top == SIZE - 1)
      cout << "Stack Overflow" << endl;
      return;
    
    arr[++top] = x;
    cout << "Element pushed to stack: " << x << endl;
  }
  void pop(){
    if(top == -1)
      cout << "Stack Underflow" << endl;
      return;
    
    cout << "Element popped from stack: " << arr[top--] << endl;
  }
  int peek(){
    if(top == -1)
      cout << "Stack is Empty" << endl;
      return 0;
    
    return arr[top];
  }
}

C++链表实现：


class Node{
public:
  int data;
  Node* next;
};
class Stack{
private:
  Node* top;
public:
  Stack()
    top = NULL;
  
  void push(int x){
    Node* temp = new Node();
    temp->data = x;
    temp->next = top;
    top = temp;
    cout << "Element pushed to stack: " << x << endl;
  }
  void pop(){
    if(top == NULL)
      cout << "Stack Underflow" << endl;
      return;
    
    Node* temp = top;
    top = top->next;
    cout << "Element popped from stack: " << temp->data << endl;
    delete temp;
  }
  int peek(){
    if(top == NULL)
      cout << "Stack is Empty" << endl;
      return 0;
    
    return top->data;
  }
}

栈的应用：

- 编辑器中的撤销操作

- 逆波兰表达式求值

- 浏览器的前进后退操作

总结：

队列和栈是两种非常重要的数据结构，它们可以应用于各个领域。本文介绍了C++如何实现队列和栈，以及它们的应用。希望本文能对读者有所帮助。

上一篇: idea打包java可执行jar包

下一篇: C++中百分号代表什么运算？

评论区

()

相似文章