【问题描述】
栈采用链式存储，编程实现读取、进栈、出栈等基本操作。
相当于前插法
/* 链栈
实现操作：
*1 进栈
*2 出栈
*3 读栈顶元素
*4 判空
代码使用不带头结点的单链表实现链栈，
入栈、出栈操作相当于单链表在表头的
插入、删除操作。
*/
#include <iostream>
#include <cstdio>
using namespace std;
typedef int ElemType;
struct Node {
ElemType data; //栈中元素
Node* next; //下一个元素的指针
};
typedef Node* LinkStack;
//初始化一个链栈
void InitLinkStack( LinkStack& S )
{
//S永远指向栈顶元素，初始化时栈为空，S初始化为NULL
S = NULL;
}
//判空
bool StackEmpty( LinkStack S )
{
if( S == NULL )
return true;
return false;
}
//进栈:将元素x压入堆栈
bool Push( LinkStack& S, ElemType x )
{
Node* temp = new Node;
temp->data = x;
if( S == NULL ) {
S = temp;
S->next = NULL;
return true;
}
temp->next = S;
S = temp;
return true;
}
//出栈:将栈顶元素出栈，并将其值用x带回
bool Pop( LinkStack& S, ElemType& x )
{
if( S == NULL )
return false;
x = S->data;
Node* toFree = S;
S = S->next; //新栈顶
delete toFree;
return true;
}
bool GetTop( LinkStack S, ElemType x )
{
if( S == NULL )
return false;
x = S->data;
return true;
}
void test1()
{
LinkStack S;
InitLinkStack(S);
for( int i=1; i<=50; i++ ) {
if( Push(S,i) ) {
cout << "入栈成功，入栈的元素是：" << i << endl;
}
else cout << "入栈失败 " << endl;
}
cout << "-------------------------------" << endl;
while( !StackEmpty(S) ) {
int x = 0;
Pop(S,x);
cout << x << endl;
}
}
int main()
{
test1();
return 0;
}
栈是一种后进先出（Last In First Out，LIFO）的数据结构，常用的栈操作包括读取、进栈、出栈等。下面是使用链式存储实现栈操作的示例代码：
#include <stdio.h>
#include <stdlib.h>
/* 栈的结点 */
typedef struct StackNode {
int data; // 数据域
struct StackNode *next; // 指向下一个结点的指针
} StackNode;
/* 栈的结构体 */
typedef struct Stack {
StackNode *top; // 栈顶指针
} Stack;
/* 创建空栈 */
Stack *createStack()
{
Stack *stack = (Stack *)malloc(sizeof(Stack));
if (stack == NULL) {
printf("Failed to create stack\n");
return NULL;
}
stack->top = NULL;
return stack;
}
/* 判断栈是否为空 */
int isEmpty(Stack *stack)
{
return stack->top == NULL;
}
/* 读取栈顶元素 */
int peek(Stack *stack)
{
if (isEmpty(stack)) {
printf("Stack is empty\n");
return 0;
}
return stack->top->data;
}
/* 进栈 */
void push(Stack *stack, int data)
{
StackNode *node = (StackNode *)malloc(sizeof(StackNode));
if (node == NULL) {
printf("Failed to push element\n");
return;
}
node->data = data;
node->next = stack->top;
stack->top = node;
}
/* 出栈 */
int pop(Stack *stack)
{
if (isEmpty(stack)) {
printf("Stack is empty\n");
return 0;
}
StackNode *node = stack->top;
int data = node->data;
stack->top = node->next;
free(node);
return data;
}
/* 主函数 */
int main()
{
/* 创建一个空栈 */
Stack *stack = createStack();
if (stack == NULL) {
return -1;
}
/* 进栈 */
push(stack, 10);
push(stack, 20);
push(stack, 30);
/* 读取栈顶元素 */
printf("Top element of stack: %d\n", peek(stack));
/* 出栈 */
printf("Popped elements: %d %d %d\n", pop(stack), pop(stack), pop(stack));
/* 销毁栈 */
free(stack);
return 0;
}
上述代码中，我们使用了链式存储来实现栈，其中StackNode结构体表示栈的结点，Stack结构体表示整个栈。主函数中我们创建了一个空栈，然后进行了进栈、读取栈顶元素、出栈等操作。最后我们使用free函数销毁了栈，释放了内存空间。
您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！