当前位置：首页 > news >正文

浅谈【数据结构】栈和队列之栈

news 2025/7/18 7:04:09

1、栈和队列

1.1栈思想

1.2、栈存储结构分为两类

1.2.1顺序栈

1.2.2链式栈

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

1、栈和队列

栈和队列并不是一个什么具体的东西，是一种思想，建立在线性表上的一种思想。

1.1栈思想

思想：先进后出，后进先出

例如：

弹夹
- 压子弹：在弹夹的上方进来
- 发射子弹：在弹夹上方出去

1.2、栈存储结构分为两类

1.2.1顺序栈

数组+整型数据：结构体(类)
特点：栈中元素的地址是连续的。且栈空间大小是固定的。

struct seqStack {

int top; // 指向栈顶元素的下标。栈顶指针

ElementType stack[长度]; // 栈的空间（栈元素存放的空间）

};

注意：顺序栈在取元素的时候其实没有删除元素的，只是把下标移动了，在下一次增加元素就会覆盖原来的元素。

示例代码：

#include <iostream>// 栈内元素的类型
#define ElementType int// 出栈错误
#define STACKERR 0xffffffff// 定义栈顶下标宏
#define STACKBUTTOM 0// 不建议大家把结构体作为类来使用，虽然可以，但是容易混淆类和结构体概念
// 声明顺序栈的类型
typedef struct SeqStack
{int top; // 顺序栈的栈顶指针（下标）// 想让栈空间可以在创建的时候去指定，设计一个成员变量来记录最大长度int stack_max_length;ElementType stack[0];
}SeqStack_t;
/*完成对于栈的：创建栈入栈出栈销毁栈检查栈是否已满打印栈内元素
*/
/*第一种方式创建；// 局部的栈，销毁随作用域的消失而自动销毁。但是需要结合操作栈的API来使用SeqStack_t stack; 第二种方式创建：动态内存分配
*/
/*@brief 创建一个顺序栈@param maxLength 顺序栈的最大容量@return 成功返回栈的首地址,失败返回nullptr
*/
SeqStack_t *createNewSeqStack(int maxLength)
{// 为了代码好看，先求出需要空间大小int spaceLength = sizeof(SeqStack_t)+maxLength*sizeof(ElementType);// 申请一个spaceLength大小空间给到newStack,包含了栈元素空间SeqStack_t *newStack = (SeqStack_t*)new unsigned char[spaceLength];// 初始化// 第一种：top指向待插入元素newStack->top = STACKBUTTOM;newStack->stack_max_length = maxLength;/*第二种：top指向栈顶元素newStack->top = -1;*/return newStack;
}/*@brief 检查栈是否存满了@param stack 需要检查的stack的指针@return 未满返回false，已满返回true
*/
bool stackIsFull(SeqStack_t *stack)
{// 第一种：top指向待插入元素的位置if(stack->top == stack->stack_max_length) // top和最大数量相等时候，其实下标已经超出范围了return true;return false;/*第二种：top指向栈元素的位置if(stack->top == stack->stack_max_length-1)// top等于max-1原因必须要指向一个能访问的位置return true;return false;*/
}/*@brief 判断一个栈是否为空@param stack需要判断的栈指针@return 已空返回true，未空返回false
*/
bool stackIsEmpty(SeqStack_t *stack)
{// 第一种：top指向待插入元素的位置if(stack->top == STACKBUTTOM) // top和最大数量相等时候，其实下标已经超出范围了return true;return false;/*第二种：top指向栈元素的位置if(stack->top == -1)// top等于-1原因为0下标是需要存放数据return true;return false;*/
}/*@brief 对一个指定的栈进行入栈操作@param 需要入栈元素的栈指针@param 需要入栈的元素@return 成功返回true，失败返回false
*/
bool pushData(SeqStack_t*stack,ElementType data)
{// 判断栈是否已满,返回falseif(stackIsFull(stack))return false;// 栈没满// 第一种：top指向待插入元素的位置stack->stack[stack->top] = data;stack->top++;return true;/*第二种：top指向栈元素的位置stack->top++;stack->stack[stack->top] = data;return true;*/
}/*@brief 对一个指定的栈进行元素出栈@param stack需要出栈的栈指针@return 成功返回出栈元素，失败返回错误码：STACKERR
*/
ElementType popData(SeqStack_t *stack)
{// 判断栈是否空if(stackIsEmpty(stack))return STACKERR;// 返回出栈元素// 第一种：top指向待插入元素stack->top--;ElementType data = stack->stack[stack->top];return data;
}int main()
{// 创建一个栈// SeqStack_t s; // 这种方式栈结构体内不能存在柔性数组SeqStack_t * stack = createNewSeqStack(10);// 入栈pushData(stack,10);pushData(stack,1);pushData(stack,7);// 出栈ElementType data = 0;while(data != STACKERR){data = popData(stack);std::cout << data << std::endl;}// 销毁栈delete stack;return 0;return 0;
}

1.2.2链式栈

由一个单链表表示
特点：只能在表头操作（插入和删除）（插/取）。空间大小可以不固定，且地址不连续。
- 表头：以单链表为例，那么表头就是首结点（链表的第一个结点）。

示例代码：

#include <iostream>/*外部声明，不会开辟空间，在这个文件里面声明这个标识符
*/
extern struct node *addNodeHead(struct node *list,int data);typedef struct node {int data;struct node *next;
}ListStack;#define STACKERR 0xefffffff/*@brief 入栈@param stack 需要入栈的栈指针@param data 需要入栈的数据@return 成功返回true，失败返回false
*/
bool pushData(ListStack **stack,int data)
{*stack = addNodeHead(*stack,data);return true;
}/*@brief 出栈@param stack 需要出栈的栈指针@return 成功返回出栈元素，失败返回STACKERR错误用二级指针的原因：1、首先出栈：首结点是会改变的吧，相当于单链表的首地址改变了。2、需要更新链表指针对于首结点的指向问题：返回值可以修改链表的指针指向的，但是此时的返回值被出栈元素占用了。解决：只能通过参数来解决修改指向操作3、在形参中，同级（同类型）是无法让形参改变实参的解决：只能通过指针/引用的方式来进行让所谓的形参去改变实参这是因为stack本身就是一个一级指针，你再搞个一级指针（同级：同级（同类型）是无法让形参改变实参的）所以我们对stack进行取地址，那么拿到的类型就是一个二级指针（非同级（非同类型））。*/
int popData(ListStack **stack)
{// 判断栈是否为空if(!(*stack))return STACKERR;// 出栈// 取出数据int data = (*stack)->data;// 断开结点ListStack *node_ptr = *stack;// 更新栈顶指针*stack = (*stack)->next;// 释放出栈的结点delete  node_ptr;return data;
}bool destoryListStack(ListStack **stack)
{if(!*stack)return false;std::cout << "开始销毁：" <<std::endl;// 销毁while(*stack) // 不停的出栈，直到为空std::cout << popData(stack) << std::endl;return true;
}int main()
{// 创建一个空栈ListStack *stack = nullptr;// 入栈pushData(&stack,10);pushData(&stack,9);pushData(&stack,8);pushData(&stack,7);// 出栈int data = popData(&stack);std::cout << data << std::endl;data = popData(&stack);std::cout << data << std::endl;data = popData(&stack);std::cout << data << std::endl;// 销毁destoryListStack(&stack);return 0;
}

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
struct node
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct node *next;
};/*@brief: 尾部插入@param: list 需要增加新数据的链表指针@param: data 是需要存入链表的数据@return : 链表首地址
*/
struct node* addNodeTail(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 搞一个临时指针，来指向首结点struct node *node_ptr = list;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;return list;
}/*@brief : 中间插入法@param : list 需要增加数据的链表首地址@param : data 需要增加到链表的数据@return : 链表首地址
*/
struct node *addNodeMid(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 循环比较数据 大到小  小到大// struct node *node_previce = nullptr;// struct node *node_current = list;// 第一种方法两个指针// while(node_current)// {//     if(node_current->data > data)//         break; // 找到插入位置了//     // 把两个指针往后移//     node_previce = node_current;//     node_current = node_current->next;// }// // 进行插入// if(node_previce == nullptr) // 说明需要作为首结点插入（头插入)// {//     // 头插代码// }// else// {//     // 直接插入到node_previce的后面//     newNode->next = node_previce->next; // 要成为node_previce下一个结点的前驱结点//     node_previce->next = newNode; // 然后让newNode成为node_previce的后继结点// }// 第二种方法提前判断struct node *node_ptr = list;// 如果第一个结点就比data大说明要插入到最前面（头插法）if(node_ptr->data > data){// 头插法return list;} while(node_ptr&&node_ptr->next){std::cout << node_ptr->data << std::endl;if(node_ptr->data < data && node_ptr->next->data >= data) // 大于前一个小于后一个{// 将新结点的next指向当前结点的后继结点node_ptr->nextnewNode->next = node_ptr->next;// 让newNode成为node_ptr的后继结点node_ptr->next = newNode;return list; // 退出增加}// 把指针往后移node_ptr = node_ptr->next;}// 严谨判断一下node_ptr->next是不是为空if(node_ptr->next == nullptr) // 尾插法{node_ptr->next = newNode;}return list;
}/*@brief 头部插入法@parma list 需要增加数据的链表首地址@param data 需要增加到链表的数据@return 链表首地址
*/
struct node *addNodeHead(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data;newNode->next = list;return newNode;
}/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct node *createNewList()
{// 新链表的首结点指针struct node *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 做第一次判断：链表中有没有结点if(newList == nullptr){struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue;}// 通过中间插入法增加结点newList = addNodeMid(newList,data);// 通过尾插法增加结点// newList = addNodeTail(newList,data);}return newList;
}// 打印链表（遍历方法）
void printList(struct node *list)
{// 判断是不是空链表if(list == nullptr){std::cout << "链表为空" << std::endl;return;}std::cout << "List( ";// 如果不为空打印链表元素while(list) // 只要list不为空就一直循环{// list本来就可以表示首结点std::cout << list->data << " ";// 让list移动到下一个结点list = list->next;}std::cout << ")" << std::endl;
}// int main()
// {
//     // 不在栈空间里面申请结点空间
//     // 创建一个链表
//     struct node *newList = createNewList();//     // 打印链表元素
//     printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址
//     return 0;
// }

查看全文

http://www.mrgr.cn/news/14624.html