数据结构进阶——使用数组实现栈和队列详解与示例（C，C#，C++）

文章目录

1、数组实现栈
- 栈的基本操作
- C语言实现
- C#语言实现
2、数组实现队列
- 队列的基本操作
- C语言实现
- C# 语言实现
- C++语言实现
总结

在编程世界中，数据结构是构建高效算法的基石。栈和队列作为两种基本的数据结构，它们的应用非常广泛。本文将带领大家使用C，C#和C++三种编程语言，通过数组来实现栈和队列，并提供详细的代码示例。

1、数组实现栈

栈是一种后进先出（Last In First Out, LIFO）的数据结构。使用数组实现栈的基本思路如下：

定义一个数组来存储栈中的元素。
定义一个变量来表示栈顶位置。

栈的基本操作

初始化：创建一个固定大小的数组，并将栈顶位置初始化为-1。
入栈（push）：将元素放入栈顶，并将栈顶位置加1。
出栈（pop）：移除栈顶元素，并将栈顶位置减1。
查看栈顶元素（peek）：返回栈顶元素，但不移除它。
判断栈是否为空（isEmpty）：如果栈顶位置为-1，则栈为空。
判断栈是否满（isFull）：如果栈顶位置等于数组长度-1，则栈满。

C语言实现

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100typedef struct Stack {int data[MAX_SIZE];int top;
} Stack;void initializeStack(Stack *s) {s->top = -1;
}bool isFull(Stack *s) {return s->top == MAX_SIZE - 1;
}bool isEmpty(Stack *s) {return s->top == -1;
}void push(Stack *s, int value) {if (isFull(s)) {printf("栈已满，无法入栈\n");return;}s->data[++s->top] = value;
}int pop(Stack *s) {if (isEmpty(s)) {printf("栈为空，无法出栈\n");return -1;}return s->data[s->top--];
}int peek(Stack *s) {if (isEmpty(s)) {printf("栈为空\n");return -1;}return s->data[s->top];
}int main() {Stack s;initializeStack(&s);push(&s, 10);push(&s, 20);printf("栈顶元素：%d\n", peek(&s));printf("出栈元素：%d\n", pop(&s));return 0;
}

C#语言实现

using System;public class Stack {private int[] data;private int top;private int maxSize;public Stack(int size) {maxSize = size;data = new int[maxSize];top = -1;}public bool IsFull() {return top == maxSize - 1;}public bool IsEmpty() {return top == -1;}public void Push(int value) {if (IsFull()) {Console.WriteLine("栈已满，无法入栈");return;}data[++top] = value;}public int Pop() {if (IsEmpty()) {Console.WriteLine("栈为空，无法出栈");return -1;}return data[top--];}public int Peek() {if (IsEmpty()) {Console.WriteLine("栈为空");return -1;}return data[top];}
}class Program {static void Main() {Stack s = new Stack(100);s.Push(10);s.Push(20);Console.WriteLine("栈顶元素：" + s.Peek());Console.WriteLine("出栈元素：" + s.Pop());}
}

C++语言实现

#include <iostream>
#include <vector>
using namespace std;class Stack {
private:vector<int> data;int top;int maxSize;public:Stack(int size) : maxSize(size), top(-1) {data.resize(maxSize);}bool isFull() const {return top == maxSize - 1;}bool isEmpty() const {return top == -1;}void push(int value) {if (isFull()) {cout << "栈已满，无法入栈" << endl;return;}data[++top] = value;}int pop() {if (isEmpty()) {cout << "栈为空，无法出栈" << endl;return -1;}return data[top--];}int peek() const {if (isEmpty()) {cout << "栈为空" << endl;return -1;}return data[top];}
};int main() {Stack s(100);s.push(10);s.push(20);cout << "栈顶元素：" << s.peek() << endl;cout << "出栈元素：" << s.pop() << endl;return 0;
}

2、数组实现队列

队列是一种先进先出（First In First Out, FIFO）的数据结构。使用数组实现队列的基本思路如下：

定义一个数组来存储队列中的元素。
定义两个变量分别表示队列头部和尾部。

队列的基本操作

初始化：创建一个固定大小的数组，并将队列头部和尾部位置初始化为0。
入队（enqueue）：在队列尾部添加元素，并将尾部位置加1。
出队（dequeue）：移除队列头部元素，并将头部位置加1。
查看队列头部元素（front）：返回队列头部元素，但不移除它。
判断队列是否为空（isEmpty）：如果头部和尾部位置相同，则队列为空。
判断队列是否满（isFull）：如果尾部位置等于数组长度，则队列满。

C语言实现

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100typedef struct Queue {int data[MAX_SIZE];int front;int rear;
} Queue;void initializeQueue(Queue *q) {q->front = 0;q->rear = 0;
}bool isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}bool isEmpty(Queue *q) {return q->rear == q->front;
}void enqueue(Queue *q, int value) {if (isFull(q)) {printf("队列已满，无法入队\n");return;}q->data[q->rear] = value;q->rear = (q->rear + 1) % MAX_SIZE;
}int dequeue(Queue *q) {if (isEmpty(q)) {printf("队列为空，无法出队\n");return -1;}int value = q->data[q->front];q->front = (q->front + 1) % MAX_SIZE;return value;
}int front(Queue *q) {if (isEmpty(q)) {printf("队列为空\n");return -1;}return q->data[q->front];
}int main() {Queue q;initializeQueue(&q);enqueue(&q, 10);enqueue(&q, 20);printf("队首元素：%d\n", front(&q));printf("出队元素：%d\n", dequeue(&q));return 0;
}

C# 语言实现

using System;public class Queue {private int[] data;private int front;private int rear;private int maxSize;public Queue(int size) {maxSize = size;data = new int[maxSize];front = 0;rear = 0;}public bool IsFull() {return (rear + 1) % maxSize == front;}public bool IsEmpty() {return rear == front;}public void Enqueue(int value) {if (IsFull()) {Console.WriteLine("队列已满，无法入队");return;}data[rear] = value;rear = (rear + 1) % maxSize;}public int Dequeue() {if (IsEmpty()) {Console.WriteLine("队列为空，无法出队");return -1;}int value = data[front];front = (front + 1) % maxSize;return value;}public int Front() {if (IsEmpty()) {Console.WriteLine("队列为空");return -1;}return data[front];}
}class Program {static void Main() {Queue q = new Queue(100);q.Enqueue(10);q.Enqueue(20);Console.WriteLine("队首元素：" + q.Front());Console.WriteLine("出队元素：" + q.Dequeue());}
}

C++语言实现

#include <iostream>
#include <vector>
using namespace std;class Queue {
private:vector<int> data;int front;int rear;int maxSize;public:Queue(int size) : maxSize(size), front(0), rear(0) {data.resize(maxSize);}bool isFull() const {return (rear + 1) % maxSize == front;}bool isEmpty() const {return rear == front;}void enqueue(int value) {if (isFull()) {cout << "队列已满，无法入队" << endl;return;}data[rear] = value;rear = (rear + 1) % maxSize;}int dequeue() {if (isEmpty()) {cout << "队列为空，无法出队" << endl;return -1;}int value = data[front];front = (front + 1) % maxSize;return value;}int front() const {if (isEmpty()) {cout << "队列为空" << endl;return -1;}return data[front];}
};int main() {Queue q(100);q.enqueue(10);q.enqueue(20);cout << "队首元素：" << q.front() << endl;cout << "出队元素：" << q.dequeue() << endl;return 0;
}