栈
基本定义
栈是一种基本的数据结构，它遵循“先进后出”的原则，即最后压入栈的元素最先弹出。栈可以用数组或链表来实现，常见的栈操作包括：
压栈（Push）：将一个元素放入栈顶，成为新的栈顶。
弹栈（Pop）：将栈顶元素取出，并将其从栈中删除。
获取栈顶元素（Top）：返回当前栈顶元素，但不删除它。
判断栈是否为空（IsEmpty）：判断栈中是否有元素。
栈可以由顺序和链式两种存储结构实现
顺序栈
采用顺序存储的栈称为顺序栈，利用一组地址连续的存储单元存放自栈底到栈顶的数据元素。设置一个栈顶指针top指示当前栈顶元素的位置。
/**
* @file array_stack.cpp
* @author icecreamovo (www.icecreamovo.top)
* @brief 顺序栈：使用数组实现的栈
* @version 0.1
* @date 2023-04-23
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
#define N 5
#define MAX_SIZE 5
using namespace std;
typedef struct
{
int data[MAX_SIZE];
int top; // 栈顶指针
} Stack;
void initStack(Stack *stack)
{
stack->top = -1;
}
/**
* 函数“push”将一个整数值添加到堆栈数据结构中，并打印一条消息指示操作是否成功。
*
* @param stack 指向 Stack 结构的指针，它包含一个整数数组和一个指示堆栈顶部索引的变量。
* @param val val 是需要压入堆栈的整数值。
*
* @return 如果条件 `stack->top == MAX_SIZE - 1` 为真，函数返回而不将值压入堆栈。否则，该函数会将值压入堆栈并打印一条成功消息，但不会显式返回任何内容。
*/
void push(Stack *stack, int val)
{
if (stack->top == MAX_SIZE - 1)
{
cout << "栈满，无法入栈" << endl;
return;
}
stack->data[++(stack->top)] = val;
cout << "入栈成功" << endl;
}
/**
* 如果栈为空，则打印错误信息并返回-1；否则，返回栈顶元素并递减栈顶指针
*
* @param stack 要操作的栈
*
* @return 栈顶元素。
*/
int pop(Stack *stack)
{
if (stack->top == -1)
{
cout << "栈空，无法出栈" << endl;
return -1;
}
return stack->data[(stack->top)--];
}
/**
* 如果栈顶等于-1，则栈为空
*
* @param stack 要检查的堆栈。
*
* @return 栈顶
*/
bool empty(Stack *stack)
{
return stack->top == -1;
}
void destroy(Stack *stack)
{
free(stack);
}
int main()
{
Stack *stack = (Stack *)malloc(sizeof(Stack));
initStack(stack);
for (int i = 0; i < 10; i++)
{
push(stack, i + 1);
}
while (!empty(stack))
{
cout << pop(stack) << endl;
}
destroy(stack);
system("pause");
return 0;
}共享栈
如果利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间。将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
#include <bits/stdc++.h>
#define MAX_SIZE 100
using namespace std;
// 实现共享栈
/**
* 定义了一个名为 ShareStack 的结构，它表示一个具有两个顶部的共享堆栈。
* @property {int} data - 存储堆栈元素的整数数组。
* @property {int} top1 - 共享堆栈实现中第一个堆栈的顶部索引。
* @property {int} top2 - “ShareStack”结构中的“top2”属性是共享堆栈实现中第二个堆栈的顶部指针。
* 在共享堆栈中，两个堆栈共享同一个底层数组，“top1”和“top2”指针跟踪每个堆栈的顶部元素
*/
typedef struct Stack
{
int data[MAX_SIZE];
int top1;
int top2;
} ShareStack;
/**
* 该函数通过将顶部指针设置为 -1 和 MAX_SIZE 来初始化共享堆栈。
*
* @param stack 指向 ShareStack 结构的指针，其中包含两个整数变量 top1 和 top2。
*/
void initStack(ShareStack *stack)
{
stack->top1 = -1;
stack->top2 = MAX_SIZE;
}
void push(ShareStack *stack, int val, int stackNumber)
{
if (stack->top1 + 1 == stack->top2)
{
cout << "栈满，无法入栈" << endl;
return;
}
if (stackNumber == 1)
{
stack->data[++stack->top1] = val;
}
else if (stackNumber == 2)
{
stack->data[--stack->top2] = val;
}
else
{
cout << "请输入正确的栈号" << endl;
}
}
void pop(ShareStack *stack, int stackNumber)
{
if (stackNumber == 1)
{
if (stack->top1 == -1)
{
cout << "栈1空，无法出栈" << endl;
return;
}
cout << "栈1出栈元素：" << stack->data[stack->top1--] << endl;
}
else if (stackNumber == 2)
{
if (stack->top2 == MAX_SIZE)
{
cout << "栈2空，无法出栈" << endl;
return;
}
cout << "栈2出栈元素：" << stack->data[stack->top2++] << endl;
}
else
{
cout << "请输入正确的栈号" << endl;
}
}
int main()
{
ShareStack *stack = (ShareStack *)malloc(sizeof(ShareStack));
initStack(stack);
for (int i = 0; i < 10; i++)
{
push(stack, i, 1);
}
for (int i = 0; i < 10; i++)
{
push(stack, i, 2);
}
for (int i = 0; i < 10; i++)
{
pop(stack, 1);
}
for (int i = 0; i < 10; i++)
{
pop(stack, 2);
}
system("pause");
return 0;
}链栈
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，并且不存在栈满上溢的情况。
/**
* @file linked_stack_head.cpp
* @author icecreamovo (www.icecreamovo.top)
* @brief 带头结点的单链表实现的链栈
* @version 0.1
* @date 2023-04-23
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
#define N 100
using namespace std;
/**
* 上述类型定义了一个堆栈节点结构，其中包含整数数据和指向下一个节点的指针。
* @property {int} data - 一个整型变量，存储栈中节点的数据。
* @property next - “next”是指向链表中下一个节点的指针。在这种情况下，它指向堆栈中的下一个节点。
*/
typedef struct StackNode
{
int data;
struct StackNode *next;
} StackNode, LinkStack;
/**
* 初始化堆栈。
*
* @param stack 要初始化的栈
*/
void initStack(LinkStack *stack)
{
stack->next = NULL;
}
/**
* 将值压入堆栈。
*
* @param stack 要压入的栈
* @param val 要压入堆栈的值
*/
void push(LinkStack *stack, int val)
{
StackNode *p = (StackNode *)malloc(sizeof(StackNode));
p->data = val;
p->next = stack->next;
stack->next = p;
cout << "元素：" << val << "入栈成功" << endl;
}
/**
* 函数“pop”从链接的堆栈中删除顶部元素，如果堆栈为空则返回错误消息。
*
* @param stack 指向链接堆栈的顶部节点的指针。
*
* @return 什么都没有（无效）。
*/
void pop(LinkStack *stack)
{
if (stack->next == NULL)
{
cout << "栈空，无法出栈" << endl;
return;
}
StackNode *p = stack->next;
stack->next = p->next;
free(p);
}
bool empty(LinkStack *stack)
{
return stack->next == NULL;
}
/**
* 该函数通过释放其所有节点来销毁链接堆栈。
*
* @param stack 指向 LinkStack 结构的指针，它表示堆栈的链表实现。
*/
void destroy(LinkStack *stack)
{
while (stack->next != NULL)
{
StackNode *p = stack->next;
stack->next = p->next;
free(p);
}
}
int main()
{
LinkStack *stack = (LinkStack *)malloc(sizeof(LinkStack));
initStack(stack);
for (int i = 0; i < 10; i++)
{
push(stack, i);
}
while (!empty(stack))
{
cout << stack->next->data << endl;
pop(stack);
}
destroy(stack);
system("pause");
return 0;
}Last updated
