美文网首页
限定性线性表的栈（Stack）

限定性线性表的栈（Stack）

作者: fastcv | 来源:发表于2019-08-06 22:36 被阅读0次

    前言

    栈作为一种限定性线性表，是将线性表的插入和删除操作限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶（Top）,因此栈顶的当前位置是动态变化的，它是由一个称为栈顶指针的位置指示器来指示。同时，表的另外一端被称为栈底（Bottom）。当栈中没有元素时称为空栈。栈的插入操作被形象第称为进栈或入栈，删除操作称为出栈或退栈。

    每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出（Last In First Out，LIFO）的线性表。

    示意图

    限定性线性表的栈的表示

    顺序栈

    定义类似于顺序表

    1、定义一个节点（使用结构体）

    seqstack.h

    #ifndef _SEQ_STACK_ 
#define _SEQ_STACK_ 
#define STACK_SIZE 50
typedef struct
{
    int elem[50];
    int top;
}Node,*SeqStack;
SeqStack initStack(SeqStack S);   //初始化栈
void clearStack(SeqStack S);   //清空栈 
bool isEmpty(SeqStack S);   //判断栈是否为空 
bool isFull(SeqStack S);   //判断栈是否满了
void push(SeqStack S,int data);   //添加元素
void pop(SeqStack S,int x);   //弹出栈顶元素 
void getTop(SeqStack S,int x);   //得到栈顶元素 
#endif

    2、完成相应的方法

    seqstack.cpp

    #include "SeqStack.h" 
#include <stdio.h>
#include <malloc.h>
SeqStack initStack(SeqStack S)   //初始化栈
{
    if(S != NULL)
    {
        printf("the SeqStack is inited!\n");
        return S;
    }
    S = (SeqStack)malloc(sizeof(Node));
    S->top=-1;
    printf("init Success!\n");
    return S;
}
void clearStack(SeqStack S)   //清空栈
{
    S->top = -1;
} 
bool isEmpty(SeqStack S)   //判断栈是否为空
{
    return S->top==-1;
} 
bool isFull(SeqStack S)   //判断栈是否满了
{
    return S->top==STACK_SIZE-1;
}
void push(SeqStack S,int data)   //添加元素
{
    if(S->top == STACK_SIZE -1)
    {
        printf("the SeqStack is Fulled ! \n");
        return;
    }
    S->top++;
    S->elem[S->top] = data;
    printf("push Success!\n");
}
void pop(SeqStack S,int *x)   //弹出栈顶元素
{
    if(S->top == -1)
    {
        printf("the SeqStack is empty! \n");
        return;
    }
    *x = S->elem[S->top];
    S->top--;
} 
void getTop(SeqStack S,int *x)   //得到栈顶元素 
{
    if(S->top == -1)
    {
        printf("the SeqStack is empty! \n");
        return;
    }
    *x = S->elem[S->top];
}

    3、运行查看结果

    seqstackmain.cpp

    #include "SeqStack.cpp"
#include <stdio.h>
int main()
{
    SeqStack S = NULL;
    S = initStack(S);
    
    if(isEmpty(S))
       printf("the Stack is empty \n");
    S = initStack(S);
    push(S,231);
    
    if(isEmpty(S))
       printf("the Stack is empty \n");
    int value;
    
    pop(S,&value);
    printf("the pop value is %6d \n",value);
    
    value = 0;
    getTop(S,&value);
    printf("the top value is %6d \n",value);
    return 0;
}

    运行结果：

    init Success!
the Stack is empty
the SeqStack is inited!
push Success!
the pop value is    231
the SeqStack is empty!
the top value is      0

--------------------------------
Process exited with return value 0
Press any key to continue . . .

    双端栈

    利用栈“栈底”位置不变，而栈顶的位置动态的变化的特性，首先申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶是动态变化的，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享要比两个栈分别 M/2的空间利用率要高。

    1、定义一个结点

    DqStack.h

    #ifndef _DQSTACK_H_
#define _DQSTACK_H_
#define M 100
typedef struct
{
    int stack[M];
    int top[2];
}Node,*DqStack;
DqStack initDqStack(DqStack D);   //初始化双端栈
void pushDq(DqStack S,int data,int pos);   //进栈操作
int popDq(DqStack S,int *x,int pos);   //出栈操作 
#endif
    2、实现相应的方法

    DqStack.cpp

    #include<stdio.h>
#include "DqStack.h"
#include<malloc.h>
DqStack initDqStack(DqStack D)   //初始化双端栈
{
    D = (DqStack)malloc(sizeof(DqStack));
    D->top[0] = -1;
    D->top[1] = M;
    printf("init Success! \n");
    return D;
}
void pushDq(DqStack S,int data,int pos)   //进栈操作
{
    switch(pos)
    {
        case 0:
            S->top[0]++;
            S->stack[S->top[0]] = data;
            break;
        case 1:
            S->top[1]--;
            S->stack[S->top[1]] = data;
            break;
        default:
            printf("error (loc isn't exsist!) \n");
    }
}
int popDq(DqStack S,int *x,int pos)   //出栈操作 
{
    switch(pos)
    {
        case 0:
            *x = S->stack[S->top[0]];
            S->top[0]--;
            break;
        case 1:
            *x = S->stack[S->top[1]];
            S->top[1]++;
            break;
        default:
            printf("error (loc isn't exsist!) \n");
    }
    return 0;
}
    3、运行查看结果

    DqStackMain.cpp

    #include <stdio.h>
#include "DqStack.cpp"
int main()
{
    DqStack D = NULL;
    D = initDqStack(D);
    pushDq(D,123,0);
    pushDq(D,3453,1);
    int value = 0;
    popDq(D,&value,1);
    printf("value is %6d",value);
    return 0;
}

    结果为：

    init Success!
value is   3453
--------------------------------
Process exited with return value 0
Press any key to continue

    链栈

    链栈即采用链表作为存储结构实现的栈。为了便于操作，我们使用的是待头结点的单链表实现栈。由于栈的插入和删除操作仅仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。

    1、定义一个结点

    LinkStack.h

    #ifndef _LINKSTACK_H_
#define _LINKSTACK_H_ 
typedef struct Node
{
    int data;
    Node *next;
}Node,*LinkStack;

LinkStack initStack(LinkStack L);   //初始化栈
void clearStack(LinkStack L);   //清空栈 
bool isEmpty(LinkStack L);   //判断栈是否为空 
void push(LinkStack L,int data);   //添加元素
void pop(LinkStack L,int x);   //弹出栈顶元素 
void getTop(LinkStack L,int x);   //得到栈顶元素 
#endif
    2、实现相应的方法

    LinkStack.cpp

    #include <stdio.h>
#include <malloc.h>
#include "LinkStack.h"
LinkStack initStack(LinkStack L)   //初始化栈
{
    L = (LinkStack)malloc(sizeof(Node));
    L->data = 0;
    L->next = NULL;
    printf("init Success! \n");
    return L;
}
void clearStack(LinkStack L)   //清空栈
{
    L->next = NULL;
    L->data = 0;
}
bool isEmpty(LinkStack L)   //判断栈是否为空 
{
    return L->data==0;
}
void push(LinkStack L,int data)   //添加元素，此处采用头插法
{
    LinkStack temp,p;
    temp = (LinkStack)malloc(sizeof(Node));
    temp->data = data;
    p = L->next;
    temp->next = p;
    L->next = temp;
    L->data++; 
    printf("push Success! \n");
} 
void pop(LinkStack L,int *x)   //弹出栈顶元素 
{
    LinkStack temp = L->next;
    L->data--;
    L->next= temp->next;
    *x =  temp->data;
}
void getTop(LinkStack L,int *x)   //得到栈顶元素
{
    LinkStack temp = L->next;
    *x = temp->data;
}
    3、运行查看结果

    LinkStackMain.cpp

    #include <stdio.h>
#include "LinkStack.cpp"
int main()
{
    LinkStack L = NULL;
    L = initStack(L);
    push(L,1234);
    push(L,223);
    push(L,25435);
    push(L,324);
    int value = 0;
    for(int i=0;i<4;i++)
    {
        pop(L,&value);
        printf("value is %6d \n",value);
    }
    if(isEmpty(L))
       printf("the LinkStack is empty ! \n");
    return 0;
}

    运行

    init Success!
push Success!
push Success!
push Success!
push Success!
value is    324
value is  25435
value is    223
value is   1234
the LinkStack is empty !

--------------------------------
Process exited with return value 0
Press any key to continue . . .

    相关文章

      网友评论

          本文标题：限定性线性表的栈（Stack）

          本文链接：https://www.haomeiwen.com/subject/jiqjhctx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|限定性线性表的栈（Stack）|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！