#include<iostream>
#include<cstdlib>
#define LEN sizeof(struct Node)
using namespace std;

第一、基本概念

//  栈的链表实现
#include <cstdio>
#include <cstdlib>
//#define _OJ_

定义

package com.company;

import java.util.Iterator;

/**
 * Created by bbw on 2017/7/13.
 * 下压堆栈,链表实现
 * 实现长度、pop、push、非空
 */
public class Stack<Item> implements Iterable<Item> {

    private Node first;
    private int length;
    private class Node{
        Item item;
        Node next;
    }

    public boolean isEmpty(){
        //非空
        return length == 0;
    }

    public void push(Item item){
        //加入
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        length++;
    }

    public Item pop(){
        //删除
        Item item = first.item;
        first = first.next;
        if (isEmpty())
            first = null;
        length--;
        return item;
    }


    @Override
    public Iterator<Item> iterator() {

        return new ListIterator() ;
    }
    private class ListIterator<Item> implements Iterator<Item>{

        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public Item next() {

            Item item = (Item) current.item;
            current = current.next;
            return item;
        }

        public void remove() {

        }
    }
}

package com.company;

import java.util.Iterator;

/**
 * Created by bbw on 2017/7/13.
 * 队列实现
 * 实现长度、非空、添加、删除
 */
public class Queue<Item> implements Iterable<Item>{


    private Node first;
    private Node last;
    private int length = 0;

    private class Node{
        Item item;
        Node next;
    }

    public boolean isEmpty(){
        return length ==0;
    }

    public void enQueue(Item item){
        //添加
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty())
            last = first;
        else
            oldLast.next = last;
        length++;
    }

    public Item deQueue(){
        //删除
        Item item = first.item;
        first = first.next;
        if (isEmpty()){
            last = null;
        }
        length--;
        return item;

    }
    @Override
    public Iterator<Item> iterator() {

        return new ListIterator() ;
    }
    private class ListIterator<Item> implements Iterator<Item>{

        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public Item next() {

            Item item = (Item) current.item;
            current = current.next;
            return item;
        }

        public void remove() {

        }
    }
}

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Position;

栈中的元素遵守“先进后出”的原则(LIFO,Last In First Out)

typedef struct Lnode
{
    int data;
    struct Lnode *next;
} Lnode, *stack;


值得注意next方法会返回当前节点的item 并移向下一节点。

struct Node         //节点 
{
int Element ;
struct Node *Next;
};

  只能在栈顶进行插入和删除操作

stack
creat_list(stack s)
{
    s = (stack) malloc (sizeof(Lnode));
    s->next = NULL;
}

 

int IsEmpty(Position Top);  //检验空栈 
void GetStackTop(Position Top); //获取栈顶元素 
Position Create(void);  //创建一个栈 
void Traverse(Position Top); //遍历 
void Push(Position Top);  //出栈 
void Pop(Position Top);   //入栈 

  压栈即push,将数据放入栈顶并将栈顶指针加一

int
isEmpty(stack s)
{
    if(s->next == NULL)
    return 1;
    else return 0;
}

 

int main()  //测试 
{
Position Top=Create();
Traverse(Top);
Push(Top);
return 0;
}

  出栈即pop,将数据从栈顶删除并将栈顶指针减一

void
push(int x,stack s)
{
    stack p;
    p = (stack) malloc (sizeof(Lnode));
    p->data = x;
    p->next = s->next;
    s->next = p;
    printf(“%d\n”, x);
}

  从上一篇我们知道,栈(stack)是一个只允许一端进行删除插入操作的线性表。同时,我们联想到线性表的链式结构,其特点是用一组任意的存储单元存储线性表的数据元素,因此我们选择使用链表去实现栈,规定这种实现办法叫做链栈。

int IsEmpty(Position Top) 
{
return Top->Next==NULL;  
}

  栈的基本操作有:poppush判断空获取栈顶元素求栈大小

int
pop(stack s)
{
    int e;
    stack p;
    p = s->next;
    e = p->data;
    s->next = p->next;
    free(p);
    return e;
}

  

Position Create(void)
{
int i,a[8]={15,16,21,9,54,66,24,59}; //创建一个8个元素的栈 
Position Top=NULL;
Top=(struct Node *)malloc(LEN);
Top->Next=NULL;
Top->Element=0;
for(i=0;i<8;i++)
{

图片 1

int main(int argc, char const *argv[]) {
#ifndef _OJ_  //ONLINE_JUDGE
    freopen(“input.txt”, “r”, stdin);
#endif

主要过程

Position New=(struct Node *)malloc(LEN);
   if(New==NULL)
       cout <<“空间不足” <<endl ;
   New->Element=a[i];  //赋值 
   New->Next=Top;      //New与原先的栈顶连接 
   Top=New;            //New成为新的栈顶 
}
return Top;  
}

第二、实现方式

    int i, n, x;
    stack s;
    s = creat_list(s);
    printf(“empty == %d\n”, isEmpty(s));
    scanf(“%d”, &n);
    for(i = 0;i < n; i++) {
    scanf(“%d”, &x);
    push(x,s);
     }


void Traverse(Position Top)
{
if(IsEmpty(Top))
   cout <<“空栈!” <<endl ;
else 
{
GetStackTop(Top);
   while(Top->Next!=NULL)  //栈底连接的是NULL 
       {
       cout << Top->Element <<‘ ‘;
       Top=Top->Next;
       }
   cout <<“遍历完毕” <<endl ;
}
}

栈一般
采用数组或者链表2中方式实现,各有各的特点,我这里采用倒插法链表实现

    for(i = 0;i < n; i++) {
    printf(“pop == %d\n”, pop(s));
     }

 

void GetStackTop(Position Top)
{
if(IsEmpty(Top))
   cout <<“空栈!” <<endl ;
else
cout <<“栈顶元素是:” <<Top->Element <<endl ;
}

图片 2

    return 0;
}

 

void Push(Position Top)
{
int X;
Position New=NULL;
cout <<“请输入要入栈的元素:” ; 
cin >>X ;
New=(struct Node *)malloc(LEN);
if(New==NULL)
   cout <<“空间不足!” <<endl ;
New->Element=X;     //跟创建的时候的插入是一样的 
New->Next=Top;
Top=New;
cout <<“入栈后:” ;
Traverse(Top);
}

第三、代码实现

一.申明结构体类型

void Pop(Position Top) //出栈 
{
int X;
Position Deletion=NULL;
if(IsEmpty(Top))
   cout <<“空栈!” <<endl ;
else
{
cout <<“出栈后: ” ;
Top=Top->Next;   //栈顶的下面一个元素变成栈顶 
Traverse(Top);
}
}

图片 3图片 4

 1.node  结点结构体类型    

#pragma once#include <iostream>using namespace std;template<class T> struct node {    T value;  //储存的值    node<T>* next;    node() :next {};    node : value, next {}};template <typename T> class Stack {    int length; //入栈数量    node<T> *head; //栈的头部public:    Stack() { length = 0; head = new node<T>; }    void push; //入栈    T pop();  //出栈    T top(); //获取栈顶元素    void print(); //打印栈    int size(); //获取栈内元素个数    bool isEmpty(); //判断空};template<typename T>void Stack<T>::push {    node<T>* pnode = new node<T>;    pnode->next = head->next;    head->next = pnode;    length++;}template<typename T>T Stack<T>::pop() {    if (head->next!=NULL)    {        node<T>* pnode = head->next;        T pdata = pnode->value;        head->next = head->next->next;        delete pnode;        return pdata;    }}template<typename T>T Stack<T>::top() {    while (head->next!=NULL)    {        return head->next->value;    }}template<typename T>void Stack<T>::print() {    while (head->next != NULL)    {        head = head->next;        cout << head->value << endl;    }}template<typename T>int Stack<T>::size() {    return length;}template<typename T>bool Stack<T>::isEmpty() {    return length == 0;}
typedef struct Node
{
        SElemType data;  //SElemType 指任意数据类型,如int,float
        struct Node *next;
}node;

View Code

  

测试

 2.stack  栈结构体类型   
    

#include "pch.h"#include "Stack.h"#include <iostream>using namespace std;int main(){    Stack<int> st;    st.push(1);    st.push(2);    st.push(4);    st.print();    std::cout << "Hello World!\n"; }
typedef struct Stack
{
        struct Node *top;  //记录栈顶位置
        int count;  //记录链栈长度
}stack;

图片 5

 

二.栈初始化

 1.为结点top申请内存,这里我们假设申请到的内存的地址为为0X01。

 2.count=0

  图片 6

三.入栈

 1.定义一个node
*型变量p,为其申请内存,这里我们假设申请到的内存的地址为0x02

      图片 7

 2.将新结点串入链栈,即是新结点p指向top,p->next=stack->top,注意:指向的方向与链表有所不同,这里是指向旧结构体,即栈底

      图片 8

  3.将结点串入下一结点,即是top=p;同时count++

      图片 9

  四.出栈

   1.定义一个node
*型的变量p,令p=top,结点top串入下一结点

      图片 10

   2.把结点p
free();释放,即0X02所在的数据域与指针域与被释放。 

      图片 11 

用处 


 

 

那么初学者都会想:教练,我学了链栈能干什么?

  可以做以下projects,这些projects都是符合后进先出(LIFO)原则的:

    图片 12

 

 

代码


 

  

/*************************************************************************
    > File Name:链栈(link_stack)
    > Author: Bw98
    > Mail: 786016746@qq.com
    > Blog: www.cnblogs.com/Bw98blogs/
    > Created Time: MON 17th Jul. 2017
 ************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#define OK 1
typedef int SElemType;

typedef struct Node
{
        SElemType data;
        struct Node *next;
}node;

typedef struct Stack
{
        struct Node *top;
        int count;  //长度
}stack;

int init_stack(stack *s);  //初始化为空栈
int if_empty_stack(stack *s);
int push(stack *s,int elem);  //入栈
int pop(stack *s,SElemType *e);  //出栈
int get_top(stack *s);  //显示栈顶元素
int show_stack(stack *s);
int clear_stack(stack *s);  //链栈置空
int destroy_stack(stack *s);  //摧毁栈
int length_stack(stack *s);  //链栈长度

int main()
{
        stack s;
        SElemType elem;
        int a;
        SElemType *elem2=&a;
        init_stack(&s);
        is_empty_stack(&s);
        printf("入栈开始:\n");
        while(scanf("%d",&elem)!=EOF)
        {
                getchar();
                push(&s,elem);
        }
        show_stack(&s);
        printf("该栈的栈顶元素为:\n");
        get_top(&s);
        pop(&s,elem2);
        printf("出栈元素为:%d\n",*elem2);
        clear_stack(&s);
        is_empty_stack(&s);
        return 0;
}

int init_stack(stack *s)
{
        s->top=(node *)malloc(sizeof(node));
        s->count=0;
        return OK;
}

int is_empty_stack(stack *s)
{
        if(s->count==0)
                printf("链栈为空!\n");
        else
                printf("链栈不为空!\n");
        return OK;
}

int clear_stack(stack *s)
{
        node *p=(node *)malloc(sizeof(node));
        p=s->top;
        while(s->count)
        {
                p=s->top;
                s->top=s->top->next;
                free(p);
                s->count--;
        }
        //s->count=0;
        printf("清除完毕!\n");
        return OK;
}
int length_stack(stack *s)
{
        return s->count;
}

int push(stack *s,SElemType x)
{
        node *p=(node *)malloc(sizeof(node));
        p->next=s->top;
        s->top=p;
        s->count++;
        s->top->data=x;
        printf("已入栈\n");
        return OK;
}

int get_top(stack *s)
{
        if(s->count!=0)
        {
                 printf("%d\n",s->top->data);
        }
        else
                printf("栈为空,无法返回栈顶元素!\n");
        return OK;
}

int pop(stack *s,SElemType *e)
{
        if(s->count==0)
                printf("栈为空,无法实现出栈\n");
        else
        {
                *e=s->top->data;
                node *p=(node*)malloc(sizeof(node));
                p=s->top;
                s->top=s->top->next;
                free(p);
                printf("出栈完毕!\n");
                s->count--;
        }
        return OK;
}

int show_stack(stack *s)
{
        printf("栈内元素如下\n");

        if(s->count)
        {
                node *p=s->top;
                int i;
                for(i=1;i<=s->count;i++)
                {
                        printf("%d ",s->top->data);
                        s->top=s->top->next;
                }
                s->top=p;
        }
        if(s->count==0)
                printf("空栈,无法查看栈内元素!\n");
        return OK;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图