栈是一种基于后进先出(Last-In-First-Out,LIFO)原则的抽象数据类型(ADT)。它可以理解为一种特殊的线性数据结构,其中元素按照一定的顺序进行插入和删除操作。 栈的定义包括以下几个要点:
栈的特点是,只能在栈的顶部进行插入和删除操作。最后插入的元素将首先被删除,这与我们日常生活中的物理堆栈类似,例如书堆或者餐盘堆放等。
栈可以通过多种方式实现,常见的有以下三种方式:
选择栈的实现方式取决于具体的需求和场景。如果需要高效的随机访问和固定大小的栈,可以选择数组实现;如果需要动态大小的栈且对空间效率要求不是特别高,可以选择链表实现;如果需要兼顾随机访问和动态大小的栈,可以考虑动态数组实现。
栈在计算机科学和软件开发中有广泛的应用场景。以下是一些常见的栈的应用场景:
栈在许多算法和数据结构中都扮演着重要的角色,它们提供了一种简单且高效的数据结构,用于解决许多实际问题。熟悉栈的应用场景和使用方法有助于程序员在开发过程中更好地利用栈的特性。
#include <stdio.h>
#define MAX_SIZE 100
// 定义栈结构
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int top; // 栈顶指针
} Stack;
// 初始化栈
void initStack(Stack* stack) {
stack->top = -1; // 将栈顶指针置为初始值
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// 判断栈是否已满
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
// 入栈操作
void push(Stack* stack, int value) {
if (isFull(stack)) {
printf("Error: Stack is full.\n");
return;
}
stack->top++; // 栈顶指针加1
stack->data[stack->top] = value; // 将元素存入栈顶位置
}
// 测试入栈操作
int main() {
Stack stack;
initStack(&stack); // 初始化栈
// 入栈操作
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
// 输出栈中元素
printf("Stack elements: ");
while (!isEmpty(&stack)) {
printf("%d ", stack.data[stack.top]);
stack.top--; // 栈顶指针减1,模拟出栈操作
}
printf("\n");
return 0;
}
上述代码中,我们通过定义一个结构体 Stack
来表示栈,其中包括一个存储数据的数组 data
和一个栈顶指针 top
。initStack
函数用于初始化栈,isEmpty
函数用于判断栈是否为空,isFull
函数用于判断栈是否已满,push
函数用于进行入栈操作。在 main
函数中,我们先初始化栈,然后调用 push
函数多次进行入栈操作,并通过循环遍历栈中的元素输出结果。
Tip:除了存储栈元素本身的空间外,栈的实现可能还需要一些额外的空间来存储栈的相关信息,例如栈顶指针。但这些额外的空间也是固定的,与栈的大小无关,因此不会影响入栈操作的空间复杂度。
#include <stdio.h>
#define MAX_SIZE 100
// 定义栈结构
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int top; // 栈顶指针
} Stack;
// 初始化栈
void initStack(Stack* stack) {
stack->top = -1; // 将栈顶指针置为初始值
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// 出栈操作
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Error: Stack is empty.\n");
return -1; // 返回一个错误值
}
int value = stack->data[stack->top]; // 获取栈顶元素
stack->top--; // 栈顶指针减1,模拟出栈操作
return value;
}
// 测试出栈操作
int main() {
Stack stack;
initStack(&stack); // 初始化栈
// 入栈操作
stack.data[++stack.top] = 10;
stack.data[++stack.top] = 20;
stack.data[++stack.top] = 30;
// 出栈操作
while (!isEmpty(&stack)) {
int value = pop(&stack);
printf("Popped value: %d\n", value);
}
return 0;
}
上述代码中,我们使用结构体 Stack
表示栈,其中包含一个存储数据的数组 data
和一个栈顶指针 top
。initStack
函数用于初始化栈,isEmpty
函数用于判断栈是否为空,pop
函数用于进行出栈操作。在 main
函数中,我们先初始化栈,然后使用 stack.data[++stack.top]
将元素入栈,通过调用 pop
函数进行出栈操作,并输出出栈的元素。
Tip:出栈操作的实现相对简单,只需要更新栈顶指针并返回栈顶元素即可。当栈不为空时,我们可以通过访问栈顶指针所指向的元素获取栈顶元素的值,并将栈顶指针减1,模拟出栈操作。
#define MAX_SIZE 100 // 栈的最大容量
int stackSize = MAX_SIZE; // 栈的大小为最大容量
如果使用动态数组或链表实现栈,那么栈的大小可以通过统计栈中当前元素的数量来获取。通常,栈会维护一个变量来记录栈中元素的数量。例如,在 C 语言中,可以使用如下方式获取动态数组或链表实现的栈的大小:
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int top; // 栈顶指针
} Stack;
int stackSize = stack.top + 1; // 栈的大小为栈顶指针加1
上述代码中,我们通过 stack.top
获取栈顶指针,然后加1得到栈的大小。
Tip:栈的大小可能会受到实际内存或资源的限制,例如静态数组实现的栈受到数组的大小限制,动态数组实现的栈受到可用内存的限制,链表实现的栈受到系统内存的限制。因此,在使用栈时要注意避免栈溢出或内存溢出的情况。
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int top; // 栈顶指针
} Stack;
// 判断栈是否为空
int isEmpty(Stack* stack) {
return stack->top == -1;
}
在上述代码中,isEmpty
函数用于判断栈是否为空。如果栈顶指针 stack->top
的值为 -1,则返回 1 表示栈为空;否则,返回 0 表示栈不为空。
Tip:栈是否为空的判断应该在进行栈操作之前,以确保在空栈上执行出栈操作或访问栈顶元素时不会发生错误。
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int top; // 栈顶指针
} Stack;
// 获取栈顶元素
int top(Stack* stack) {
if (stack->top == -1) {
printf("Error: Stack is empty.\n");
return -1; // 返回一个错误值
}
return stack->data[stack->top];
}
在上述代码中,top
函数用于获取栈顶元素。如果栈顶指针 stack->top
的值为 -1,则表示栈为空,无法获取栈顶元素,会输出错误信息并返回一个错误值(这里返回 -1);否则,返回栈顶指针所指向位置的元素的值。
队列是一种常见的数据结构,它一种线性数据结构,可以通过一端(称为队尾)添加元素,通过另一端(称为队头)删除元素(先进先出FIFO原则)。新元素被添加到队尾,而元素的删除操作总是从队头进行。它的特点如下:
队列可以通过不同的实现方式来实现,常见的实现方式有以下两种:
Tip:无论是使用数组还是链表实现队列,都需要注意处理边界情况,如空队列或满队列的判断。此外,还可以使用循环队列等高级实现方式来优化队列的性能和空间利用率。
队列在计算机科学和软件开发中有许多应用场景,下面是一些常见的队列应用场景:
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int front; // 队头指针
int rear; // 队尾指针
} Queue;
// 入队操作
void enqueue(Queue* queue, int element) {
if (queue->rear == MAX_SIZE - 1) {
printf("Error: Queue is full.\n");
return;
}
queue->rear++;
queue->data[queue->rear] = element;
}
在上述代码中,enqueue
函数用于将元素添加到队列中。首先,我们检查队列是否已满,即队尾指针 queue->rear
是否达到了数组的最大索引(MAX_SIZE - 1
)。如果队列已满,则输出错误信息并返回;否则,将新元素添加到队尾指针所指向的位置,并更新队尾指针。
int dequeue(Queue* queue) {
if (queue->front > queue->rear) {
printf("Error: Queue is empty.\n");
return -1; // 返回一个表示错误的值
}
int element = queue->data[queue->front];
queue->front++;
return element;
}
在上述代码中,dequeue
函数用于执行出队操作。首先,我们检查队列是否为空,即队头指针 queue->front
是否超过了队尾指针 queue->rear
。如果队列为空,则输出错误信息并返回一个表示错误的值(在此示例中为 -1);否则,将队头指针所指向的元素作为出队元素保存,然后将队头指针向后移动一位,并返回出队元素。
int getSize(Queue* queue) {
return queue->rear - queue->front + 1;
}
在上述代码中,getSize
函数用于获取队列的大小。通过计算队尾指针 queue->rear
和队头指针 queue->front
之间的差值,再加上 1,即可得到队列中元素的数量。返回该数量即可。
Tip:上述代码假定队列的合法性已经在其他地方进行了检查,即队头指针不会超过队尾指针,否则可能会导致错误的结果。
int isEmpty(Queue* queue) {
return queue->front > queue->rear;
}
在上述代码中,isEmpty
函数用于判断队列是否为空。如果队头指针 queue->front
大于队尾指针 queue->rear
,则说明队列中没有元素,返回一个非零值表示队列为空;否则,返回零表示队列不为空。
int getFront(Queue* queue) {
if (isEmpty(queue)) {
printf("Error: Queue is empty.\n");
return -1; // 返回一个表示错误的值
}
return queue->data[queue->front];
}
在上述代码中,getFront
函数用于获取队列的队首元素。首先,我们通过调用 isEmpty
函数检查队列是否为空,如果队列为空,则输出错误信息并返回一个表示错误的值(在此示例中为 -1);否则,直接返回队头指针 queue->front
所指向的元素值。
给定一个字符串,包含若干个括号(包括圆括号、方括号和花括号),判断括号的匹配是否正确。例如,“{[()()]}” 是一个正确的匹配,而 “{[(])}” 是一个错误的匹配。
讲解:这道题可以使用栈来解决。遍历字符串的每个字符,如果遇到左括号,则将其入栈;如果遇到右括号,则判断栈顶元素是否与该右括号匹配,如果匹配则将栈顶元素出栈,否则返回错误。最后,如果栈为空,则表示括号匹配正确。
C 语言代码示例:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX_SIZE 100
bool isMatching(char left, char right) {
if ((left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}')) {
return true;
}
return false;
}
bool isValidParentheses(char* s) {
int len = strlen(s);
char stack[MAX_SIZE];
int top = -1;
for (int i = 0; i < len; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
stack[++top] = s[i];
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (top == -1 || !isMatching(stack[top], s[i])) {
return false;
}
top--;
}
}
return top == -1;
}
int main() {
char s[MAX_SIZE];
printf("请输入括号字符串: ");
scanf("%s", s);
bool isValid = isValidParentheses(s);
if (isValid) {
printf("括号匹配正确\n");
} else {
printf("括号匹配错误\n");
}
return 0;
}
设计一个支持 push、pop、top 操作,并能在常数时间内返回栈中的最小元素的栈。
讲解:这道题可以使用两个栈来实现,一个栈用于存储原始数据,另一个栈用于存储当前栈中的最小元素。每次 push 操作时,如果新元素小于等于当前最小元素栈的栈顶元素,则将新元素同时入栈到两个栈中;pop 操作时,同时将两个栈的栈顶元素出栈。
C 语言代码示例:
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE]; // 存储原始数据的栈
int minStack[MAX_SIZE]; // 存储最小元素的栈
int top; // 栈顶指针
} MinStack;
void push(MinStack* stack,
int val) {
stack->data[++stack->top] = val;
if (stack->top == 0 || val <= stack->minStack[stack->top - 1]) {
stack->minStack[stack->top] = val;
} else {
stack->minStack[stack->top] = stack->minStack[stack->top - 1];
}
}
void pop(MinStack* stack) {
if (stack->top >= 0) {
stack->top--;
}
}
int top(MinStack* stack) {
if (stack->top >= 0) {
return stack->data[stack->top];
}
return INT_MIN;
}
int getMin(MinStack* stack) {
if (stack->top >= 0) {
return stack->minStack[stack->top];
}
return INT_MIN;
}
int main() {
MinStack stack;
stack.top = -1;
push(&stack, 5);
push(&stack, 3);
push(&stack, 7);
push(&stack, 2);
printf("当前栈中的最小元素为: %d\n", getMin(&stack));
pop(&stack);
pop(&stack);
printf("当前栈中的最小元素为: %d\n", getMin(&stack));
return 0;
}
使用队列实现一个栈的下列操作:push、pop、top 和 empty。
讲解:这道题可以使用两个队列来实现一个栈。当进行 push 操作时,将元素入队到一个非空队列中;当进行 pop 操作时,将非空队列中的元素依次出队并入队到另一个空队列中,直到非空队列中只剩下一个元素,将该元素出队即为栈的顶部元素;而 top 操作则直接返回非空队列的队尾元素;empty 操作则判断两个队列是否都为空。
C 语言代码示例:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct {
int* queue1;
int* queue2;
int top;
int size;
} MyStack;
MyStack* createStack(int size) {
MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
stack->queue1 = (int*)malloc(size * sizeof(int));
stack->queue2 = (int*)malloc(size * sizeof(int));
stack->top = -1;
stack->size = size;
return stack;
}
void push(MyStack* stack, int val) {
if (stack->top < stack->size - 1) {
stack->queue1[++stack->top] = val;
}
}
void swapQueues(MyStack* stack) {
int* temp = stack->queue1;
stack->queue1 = stack->queue2;
stack->queue2 = temp;
}
void adjustQueue(MyStack* stack) {
while (stack->top > 0) {
stack->queue2[++stack->top] = stack->queue1[stack->top - 1];
}
}
void pop(MyStack* stack) {
if (stack->top >= 0) {
adjustQueue(stack);
swapQueues(stack);
stack->top--;
}
}
int top(MyStack* stack) {
if (stack->top >= 0) {
return stack->queue1[stack->top];
}
return -1;
}
bool isEmpty(MyStack* stack) {
return stack->top == -1;
}
int main() {
MyStack* stack = createStack(100);
push(stack, 5);
push(stack, 3);
push(stack, 7);
push(stack, 2);
printf("栈顶元素为: %d\n", top(stack));
pop(stack);
printf("栈顶元素为: %d\n", top(stack));
while (!isEmpty(stack)) {
pop(stack);
}
printf("栈是否为空: %d\n", isEmpty(stack));
return 0;
}
以上是三道经典的栈和队列面试题,通过这些题目的讲解和代码实现,可以加深对栈和队列的理解,并且熟悉它们的常见应用。
栈和队列是常见的数据结构,在编程和算法中起着重要的作用。它们具有不同的特点和应用场景。下面是栈和队列的总结:
栈(Stack)是一种后进先出(LIFO)的数据结构,类似于现实生活中的一摞盘子。栈的特点包括:
栈的应用场景包括:
队列(Queue)是一种先进先出(FIFO)的数据结构,类似于现实生活中排队的概念。队列的特点包括:
队列的应用场景包括:
根据需求选择合适的数据结构: