算法與數(shù)據(jù)結構系列之[棧]

棧是一種限定僅在表尾進行插入和刪除操作的線性表，其最大的特點就是后進先出(Last In First Out),簡稱LIFO結構。?？梢杂脛討B(tài)數(shù)組實現(xiàn)，也可以使用鏈表實現(xiàn)。由于棧比較簡單，這里不再詳述，僅貼出代碼。
C語言代碼：
1.Stack.c

#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100   //初始分配的存儲空間大小
#define INCREMENT 10     //存儲空間分配增量
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//順序棧的實現(xiàn)
typedef struct{
    SElemType *data;  //聲明了一個名為data的長度不確定的數(shù)組，也叫“動態(tài)數(shù)組”
    int top;  //用于棧頂指針
    int size;  //?？臻g大小  用于語義明確
}Stack;

/**
* 初始化順序棧
* @param S
* @return OK
*/
Status InitStack(Stack *S){
    S->data =(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S->data) exit(-1);
    S->top = -1;  //表示空棧
    S->size = 0;
    return OK;
}

/**
* 獲取棧的大小
* @return size
*/
int GetSize(Stack stack){
    return stack.size;
}

/**
* 判斷是否為空棧
* @param stack
* @return
*/
int IsEmpty(Stack stack){
    if(stack.size == 0)
        return TRUE;
    return FALSE;
}

/**
* 獲取棧頂元素
* @param stack
* @return
*/
int Peek(Stack stack){
    if(IsEmpty(stack))
        return ERROR;
    return stack.data[stack.top];
}

/**
* 入棧
* @param S
* @param e
* @return
*/
Status Push(Stack *S,SElemType e){
    if(S->size == STACK_INIT_SIZE)  //棧已滿，擴容
        S->data =(SElemType *)realloc(S->data,(S->size + INCREMENT) * sizeof(SElemType));
    S->top++;
    S->data[S->top] = e;
    S->size++;
    return OK;
}

/**
* 出棧
* @param S
* @param e
* @return
*/
Status Pop(Stack *S,SElemType *e){
    if(S->size == 0) //空棧
        return ERROR;
    *e = S->data[S->top];
    S->top--;
    S->size--;
    return OK;
}

/**
* 遍歷并打印輸出順序棧的元素
* @param stack
*/
void DisplayStack(Stack stack){
    if(IsEmpty(stack))
        printf("該棧為空");
    for (int i = 0; i < stack.size; ++i) {
        printf("%d ",stack.data[i]);
    }
    printf("\n");
}

//鏈棧的實現(xiàn)
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;


typedef struct LinkStack{
    LinkStackPtr top;
    int size;
}LinkStack;

/**
* 初始化鏈棧
* @param L
* @return
*/
Status InitLinkStack(LinkStack *L){
    L->top = (LinkStackPtr)malloc(sizeof(StackNode));
    //L = (LinkStack *) malloc(sizeof(LinkStack));
    L->top = NULL;
    L->size = 0;
}

/**
* 獲取鏈棧的長度
* @param linkStack
* @return
*/
int GetLinkStackSize(LinkStack linkStack){
    return linkStack.size;
}

/**
* 判斷鏈棧是否為空
* @param linkStack
* @return
*/
int IsLinkStackEmpty(LinkStack linkStack){
    if(linkStack.size == 0)
        return TRUE;
    return FALSE;
}

/**
* 鏈棧入棧
* @param L
* @param e
* @return
*/
Status PushLinkStack(LinkStack *L,SElemType e){
    LinkStackPtr  s =(LinkStackPtr) malloc(sizeof(StackNode));
    s->data = e;
    s->next = L->top;
    L->top = s;
    L->size++;
    return OK;
}

/**
* 鏈棧出棧
* @param L
* @param e
* @return
*/
Status PopLinkStack(LinkStack *L,SElemType *e){
    LinkStackPtr  p;
    if(IsLinkStackEmpty(*L))
        return ERROR;
    *e = L->top->data;
    p = L->top;
    L->top = L->top->next;
    free(p);
    L->size--;
    return OK;
}

/**
* 獲取鏈棧的棧頂元素
* @param linkStack
* @return
*/
int PeekLinkStack(LinkStack linkStack){
    return linkStack.top->data;
}

/**
* 遍歷鏈棧的所有元素
* @param stack
*/
void DisplayLinkStack(LinkStack stack){
    if(IsLinkStackEmpty(stack))
        printf("該棧為空");
    while (stack.top){
        printf("%d",stack.top->data);
        stack.top = stack.top->next;
    }
    printf("\n");
}

2.Stack.h

#ifndef TEST_STACK_H
#define TEST_STACK_H


#define STACK_INIT_SIZE 100   //初始分配的存儲空間大小
#define INCREMENT 10     //存儲空間分配增量
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//順序棧的實現(xiàn)
typedef struct{
    SElemType *data;  //聲明了一個名為data的長度不確定的數(shù)組，也叫“動態(tài)數(shù)組”
    int top;  //用于棧頂指針
    int size;  //棧空間大小  用于語義明確
}Stack;

//初始化順序棧
Status InitStack(Stack *S);
//獲取棧的大小
int GetSize(Stack stack);
//判斷棧是否為空
int IsEmpty(Stack stack);
//獲取棧頂元素
int Peek(Stack stack);
//入棧
Status Push(Stack *S,SElemType e);
//出棧
Status Pop(Stack *S,SElemType *e);
//遍歷并打印輸出順序棧的元素
void DisplayStack(Stack stack);

//鏈棧的實現(xiàn)
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack{
    LinkStackPtr top;
    int size;
}LinkStack;

//初始化一個鏈棧
Status InitLinkStack(LinkStack *L);
//獲取鏈棧長度
int GetLinkStackSize(LinkStack linkStack);
//判斷鏈棧是否為空
int IsLinkStackEmpty(LinkStack linkStack);
//鏈棧入棧
Status PushLinkStack(LinkStack *L,SElemType e);
//鏈棧出棧
Status PopLinkStack(LinkStack *L,SElemType *e);
//獲取鏈棧棧頂元素
int PeekLinkStack(LinkStack linkStack);
//遍歷并打印輸出鏈棧的元素
void DisplayLinkStack(LinkStack stack);

3.main.c

//順序棧
//初始化一個空棧
Stack stack;
InitStack(&stack);
DisplayStack(stack);
//入棧操作
Push(&stack,6);
Push(&stack,7);
Push(&stack,8);
DisplayStack(stack);
//打印棧的長度
printf("%d",GetSize(stack));
printf("\n");
//判斷該棧是否為空
printf("%d",IsEmpty(stack));
printf("\n");
//獲取棧頂元素
printf("%d",Peek(stack));
printf("\n");
//出棧
int num;
int *n = &num;
Pop(&stack,n);
DisplayStack(stack);
printf("------------------------------------------");

//鏈棧
//初始化一個鏈棧
LinkStack linkStack;
InitLinkStack(&linkStack);
printf("\n");
DisplayLinkStack(linkStack);
//入棧操作
PushLinkStack(&linkStack,4);
PushLinkStack(&linkStack,5);
PushLinkStack(&linkStack,6);
DisplayLinkStack(linkStack);
//打印鏈棧長度
printf("%d",GetLinkStackSize(linkStack));
printf("\n");
//打印鏈棧棧頂元素
printf("%d",PeekLinkStack(linkStack));
printf("\n");
//入棧
PushLinkStack(&linkStack,7);
DisplayLinkStack(linkStack);
//出棧
int element;
int *e = &element;
PopLinkStack(&linkStack,e);
DisplayLinkStack(linkStack);

4.運行結果：

該棧為空
6 7 8
3
0
8
6 7
------------------------------------------
該棧為空
654
3
6
7654
654

java代碼：
1.Stack.java

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

2.ArrayStack.java

/**
* 用動態(tài)數(shù)組實現(xiàn)棧
* @param <E>
*/
public class ArrayStack<E> implements Stack<E> {


    private Array<E> array; //聲明數(shù)組


    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }


    public ArrayStack(){
        array = new Array<>();
    }
    //獲取棧的大小
    @Override
    public int getSize() {
        return array.getSize();
    }
    //判斷棧是否為空
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
    //入棧
    @Override
    public void push(E e) {
        array.add(e);
    }
    //出棧
    @Override
    public E pop() {
        return array.remove(array.getSize()-1);
    }
    //查看棧頂元素
    @Override
    public E peek() {
        return array.get(array.getSize()-1);
    }


    @Override
    public String toString() {
       StringBuilder res = new StringBuilder();
       res.append("Stack: ");
       res.append("[");
        for (int i = 0; i <array.getSize() ; i++) {
            res.append(array.get(i));
            if(i != array.getSize()-1){
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }


    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

3.LinkedListStack.java

public class LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> linkedList;

    public LinkedListStack(){
        linkedList = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public void push(E e) {
        linkedList.addFirst(e);
    }

    @Override
    public E pop() {
        return linkedList.removeFirst();
    }

    @Override
    public E peek() {
        return linkedList.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack top  ");
        res.append(linkedList);
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);

    }
}
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容