数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用链表实现栈的 C++ 程序
栈是一个包含元素集合的抽象数据结构。栈实现了 LIFO 机制，即最后压入的元素最先弹出。栈中的一些主要操作包括：
Push（压入） - 将数据值添加到栈顶。
Pop（弹出） - 删除栈顶的数据值。
Peek（查看） - 返回栈顶的数据值。
下面给出一个使用链表实现栈的程序。
示例
#include <iostream> using namespace std; struct Node { int data; struct Node *next; }; struct Node* top = NULL; void push(int val) { struct Node* newnode = (struct Node*) malloc(sizeof(struct Node)); newnode->data = val; newnode->next = top; top = newnode; } void pop() { if(top==NULL) cout<<"Stack Underflow"<<endl; else { cout<<"The popped element is "<< top->data <<endl; top = top->next; } } void display() { struct Node* ptr; if(top==NULL) cout<<"stack is empty"; else { ptr = top; cout<<"Stack elements are: "; while (ptr != NULL) { cout<< ptr->data <<" "; ptr = ptr->next; } } cout<<endl; } int main() { int ch, val; cout<<"1) Push in stack"<<endl; cout<<"2) Pop from stack"<<endl; cout<<"3) Display stack"<<endl; cout<<"4) Exit"<<endl; do { cout<<"Enter choice: "<<endl; cin>>ch; switch(ch) { case 1: { cout<<"Enter value to be pushed:"<<endl; cin>>val; push(val); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { cout<<"Exit"<<endl; break; } default: { cout<<"Invalid Choice"<<endl; } } }while(ch!=4); return 0; }
输出
1) Push in stack 2) Pop from stack 3) Display stack 4) Exit Enter choice: 1 Enter value to be pushed: 2 Enter choice: 1 Enter value to be pushed: 6 Enter choice: 1 Enter value to be pushed: 8 Enter choice: 1 Enter value to be pushed: 7 Enter choice: 2 The popped element is 7 Enter choice: 3 Stack elements are:8 6 2 Enter choice: 5 Invalid Choice Enter choice: 4 Exit
在上面的程序中，结构体 Node 用于创建作为栈实现的链表。代码如下所示。
struct Node {
int data;
struct Node *next;
};push() 函数接收参数 val，即要压入栈的值。然后创建一个新节点，并将 val 插入到数据部分。此节点添加到链表的前面，并且 top 指向它。此部分的代码片段如下所示。
void push(int val) { struct Node* newnode = (struct Node*) malloc(sizeof(struct Node)); newnode->data = val; newnode->next = top; top = newnode; }
pop() 函数弹出栈顶的值（如果存在）。如果栈为空，则打印下溢错误。代码如下所示。
void pop() { if(top==NULL) cout<<"Stack Underflow"<<endl; else { cout<<"The popped element is "<< top->data <<endl; top = top->next; } }
display() 函数显示栈中的所有元素。这是通过使用 ptr 实现的，ptr 最初指向 top，但会遍历到栈的末尾。打印与 ptr 对应的所有数据值。代码如下所示。
void display() {
struct Node* ptr;
if(top==NULL)
cout<<"stack is empty";
else {
ptr = top;
cout<<"Stack elements are: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
cout<<endl;
}main() 函数向用户提供一个选择，询问他们是否要压入、弹出或显示栈。根据用户的响应，使用switch 调用相应的函数。如果用户输入无效的响应，则打印错误信息。此部分的代码片段如下所示。
int main() { int ch, val; cout<<"1) Push in stack"<<endl; cout<<"2) Pop from stack"<<endl; cout<<"3) Display stack"<<endl; cout<<"4) Exit"<<endl; do { cout<<"Enter choice: "<<endl; cin>>ch; switch(ch) { case 1: { cout<<"Enter value to be pushed:"<<endl; cin>>val; push(val); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { cout<<"Exit"<<endl; break; } default: { cout<<"Invalid Choice"<<endl; } } }while(ch!=4); return 0; }
更新于: 2023年9月14日
42K+ 浏览量
广告