為實習準備的資料結構（3）-- 詳解 棧

在這裡插入圖檔描述

什麼是棧

棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和删除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧删除元素又稱作出棧或退棧，它是把棧頂元素删除掉，使其相鄰的元素成為新的棧頂元素。

在這裡插入圖檔描述

①後進先出的叫棧

棧呐，你可以叫它彈（dan）棧，就像彈夾一樣。

入棧隻能在棧頂，出棧也隻能在棧頂，想象一下手槍彈夾。

也可以說，棧是一種==僅限于在表尾進行抽插的線性表==。

②API設計

類名	stack
構造方式	stack()
成員方法：
入棧（壓棧）	push(void*)
出棧（彈棧）	pop(void*)
大小擷取	size()
棧頂元素擷取	top()
成員屬性：
對于鍊棧	Node pres; Node prev; Node data;
對于線棧	int size; top

==上面預設的資料類型，為泛型。為了友善了解，接下來全用int類型==

③順序棧實作

#include <iostream>
#define StackSize 100	//棧長度

using namespace std;

class SeqStack {

private:
    int data[StackSize];	//線性棧表
    int top;	//紀錄棧頂

public:
    SeqStack(){top=-1;};    //将項頂指針置為-1
    ~SeqStack(){}

    void Push(int x){
    	if (top==StackSize-1){
			cout<<"棧滿"<<endl;
			return;
		}
		top++;
		data[top] = x;
	}

	//彈棧
    int Pop(){
    	if (top==-1){
			cout<<"棧空"<<endl;
			return;
		}
    	return data[top];
    	top--
    }	//版本1：取出棧頂元素
	//一般是用版本1，是以版本2不看了
	
    int GetTop(){
		if (top==-1){
			cout<<"棧空"<<endl;
			return;
		}
		return data[top];
	}//擷取棧頂元素

    int Empty(){
	if (top==-1) 
        return 1;
	} //判斷是否為空	
};           

複制

④雙端棧

==雙棧是指兩個順序棧，是一種特殊的順序棧。==

在這裡插入圖檔描述

• 雙棧共享一個位址連續的存儲單元。即程式同時需要兩個棧時，可以定義一個足夠大的棧空間，該空間的兩端分别設為兩個棧的棧底，用bottom0=-1和bottom1=maxSize訓示。
• 壓入資料時，讓兩個棧的棧頂top0和top1都向中間伸展，如果訓示棧頂的指針top0+1等于另一個棧頂的指針top1時兩棧已滿。
• 每次進棧時top0加1或top1減1，而退棧時top0減1或top1加1。
• 如果

  top[0] == -1

  或

  top[1] == maxSize

  ，有棧為空。

實作

#include <iostream>

using namespace std;

const int defaultSize = 50;         //預設棧空間大小
const int stackIncreament = 20;     //棧溢出時擴充空間的增量
const int n = 2;                    //設定n=2個棧共有一個棧空間

class DualStack
{
public:
    DualStack(int sz = defaultSize);        //構造函數
    ~DualStack();                           //析構函數
public:
    bool Push(const T& x, int d) ;      //新元素x進棧
    bool Pop(T& x, int d);              //棧頂元素出棧，并将該元素的值儲存至x
    bool getTop(T& x, int d) const;     //讀取棧頂元素，并将該元素的值儲存至x
    bool IsEmpty() const;               //判斷棧是否為空
    bool IsFull() const;                //判斷棧是否為滿
    int getSize() const;                //計算棧中元素個數
    void MakeEmpty();                   //清空棧的内容
    void overflowProcess();             //棧的溢出處理
    
private:
	int *vec;			//存放棧中元素
    int top[n-1];     //棧頂指針
    int maxSize;    //棧最大可容納元素個數
};

//構造函數
DualStack::DualStack(int sz)
{
    if (sz >= 0)
    {
        maxSize = sz;           
        top[0] = -1;
        top[1] = maxSize;
 		vec = new int[maxSize];
    }
}                       

//析構函數
DualStack::~DualStack()
{
    delete[] vec;
    vec = NULL;
}   

//新元素x進棧
bool DualStack::Push(const int x, int d)
{
    if (true == IsFull())
        return false;
    if (0 == d)
        top[0]++;
    else
        top[1]--;
    vec[top[d]] = x;
    return true;
}

//棧頂元素出棧，并将該元素的值儲存至x
bool DualStack::Pop(int x, int d)
{
    if (true == IsEmpty())
        return false;
    x = vec[top[d]];
    if (0 == d)
        top[0]--;
    else
        top[1]++;
    return true;
}

//讀取棧頂元素，并将該元素的值儲存至x
bool DualStack::getTop(int x, int d) const
{
    if (true == IsEmpty())
        return false;
    x = vec[top[d]];
    return true;
}

//判斷棧是否為空
bool DualStack::IsEmpty() const
{
    return ((-1 == top[0]) && (maxSize == top[1])) ? true : false;
}

//判斷棧是否為滿
bool DualStack::IsFull() const
{
    return (top[0] + 1 == top[1]) ? true : false;
}

//計算棧中元素個數
int DualStack::getSize() const
{
    return (top[0] + 1) + (maxSize - top[1]);
}

//清空棧的内容
void DualStack::MakeEmpty()
{
    delete[] vec;
    top[0] = -1;
    top[1] = maxSize;
    vec = new int[maxSize];
    //如果用vector容器的話，就直接清空了
    //但是為了普遍性，還是把STL收起來了
}

//棧的溢出處理
void DualStack::overflowProcess()
{
    int newSize = maxSize + stackIncreament;
    int *neweVector = new int[newSize];
    for (int i = 0; i <= top[0]; i++)
    {
        neweVector[i] = vec[i];
    }
    for (int i = maxSize - 1; i >= top[1]; i--)
    {
        neweVector[i + stackIncreament] = vec[i];
    }
    delete[] vec;
    vec= neweVector;
    maxSize = newSize;
    top[1] += stackIncreament;
}           

複制

多端棧

多端棧推薦使用鍊棧實作。

⑤鍊棧

鍊棧，結合了連結清單和棧的優點。

鍊棧的實作思路同順序棧類似，==通常我們将連結清單的頭部作為棧頂，尾部作為棧底==，如圖所示:

在這裡插入圖檔描述

• 将連結清單頭部作為棧頂的一端，可以避免在實作資料 "入棧" 和 "出棧" 操作時做大量周遊連結清單的耗時操作。

連結清單的頭部作為棧頂，意味着：

在實作資料"入棧"操作時，需要将資料從連結清單的頭部插入；
在實作資料"出棧"操作時，需要删除連結清單頭部的首元節點；           

複制

==是以，鍊棧實際上就是一個隻能采用頭插法插入或删除資料的連結清單。==

實作

前面都用cpp，這裡搞個c換換風格

//連結清單中的節點結構
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;           

複制

• 壓棧實作

//stack為目前的鍊棧，a表示入棧元素

lineStack* push(lineStack * stack,int a){
    //建立存儲新元素的節點
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    //新節點與頭節點建立邏輯關系
    line->next=stack;
    //更新頭指針的指向
    stack=line;
    return stack;
}           

複制

• 出棧實作

//棧頂元素對外連結棧的實作函數
lineStack * pop(lineStack * stack){
    if (stack) {
        //聲明一個新指針指向棧頂節點
        lineStack * p=stack;
        //更新頭指針
        stack=stack->next;
        printf("出棧元素：%d ",p->data);
        if (stack) {
            printf("新棧頂元素：%d\n",stack->data);
        }else{
            printf("棧已空\n");
        }
        free(p);
    }else{
        printf("棧内沒有元素");
        return stack;
    }
    return stack;
}           

複制

⑥漢諾塔

在這裡插入圖檔描述

漢諾塔：漢諾塔(Tower of

Hanoi)源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊着64片黃金圓盤。大梵天指令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。

--引用維基百科

a是起始柱，c是目标柱，b起到中轉作用           

複制

本來我是一頭霧水的，但是在力扣上被那個爬樓梯的“簡單”動态規劃題折磨之後，我有點茅廁頓開的感覺。

• 問題看起來并不複雜，當a柱子上隻有一個盤子時隻要把那個盤子直接移到c就行了。

  有兩個盤子的話把1号盤先移到b柱，在把2号盤移到c柱，最後把b柱上的1号盤移到c柱就行了。

• 這裡我們先把上方的63個盤子看成整體，這下就等于隻有兩個盤子，自然很容易了，我們隻要完成兩個盤子的轉移就行了，好了現在我們先不管第64個盤子，假設a柱隻有63個盤子，與之前一樣的解決方式，前62個盤子先完成移動目标。
• 嗯，就這樣一步步向前找到可以直接移動的盤子，62,61,60，......，2,1，最終，最上方的盤子是可以直接移動到c柱的，那就好辦了，我們的2号盤也能完成向c柱的轉移，這時c柱上時已經轉移成功的2個盤，于是3号盤也可以了，一直到第64号盤。

==這個真的刺激（燒腦），主要配合上遞歸的思想==

先看碼：

棧部分代碼，左邊有目錄，鍊棧。

void main()
{
	int n = 64;	//可以泛化
	
	Stack a = init_stack();
	Stack b = init_stack();
	Stack c = init_stack();
	while(n-->0){// 初始化棧a，代表最左邊柱子和盤子
		 push_stack(a,i); 
	}
	hanoi(n,a,b,c); 
}

void hanoi(int n,Stack a,Stack b,Stack c)
{
	if(n == 1) // 盤子數為1
		pop_push(a,c);
	else
	{
		hanoi(n-1,a,c,b); // 将棧a的n-1個盤子順序移到棧b
		pop_push(a,c); // 将棧a的第n個盤子移到棧c
		hanoi(n-1,b,c,a); // 将棧b的n-1個盤子順序移到棧c
	}
}           

複制

不行，我要去補腦。。。

⑦單調棧

之前在力扣刷題，用到單調棧，不過那時候還不知道它叫單調棧哈哈，那個賣股票的題目。

單調棧就是棧内元素單調遞增或者單調遞減的棧，單調棧隻能在棧頂操作。

性質：

• 單調棧的維護是 O(n) 級的時間複雜度，因為所有元素隻會進入棧一次，并且出棧後再也不會進棧了。
• 單調棧裡的元素具有單調性。
• ==元素加入棧前，會在棧頂端把破壞棧單調性的元素都删除==
• 使用單調棧可以找到元素向左周遊第一個比他小的元素，也可以找到元素向左周遊第一個比他大的元素。
• ==單調棧在用于維護區間距非常有優勢==。

波蘭式與逆波蘭式

什麼是波蘭表達式

人類最熟悉的一種表達式1+2，(1+2)3，3+4 2+4等等都是中綴表示法。對于人們來說，也是最直覺的一種求值方式，先算括号裡的，然後算乘除，最後算加減，但是，計算機進行中綴表達式卻并不友善，因為沒有一種簡單的資料結構可以友善從一個表達式中間抽出一部分算完結果，再放進去，然後繼續後面的計算（連結清單也許可以，但是，代價也是不菲）。

是以，1920年，波蘭科學家揚·武卡謝維奇（Jan ukasiewicz）發明了一種不需要括号的計算表達式的表示法将操作符号寫在操作數之前，也就是字首表達式，即波蘭式（Polish Notation, PN）。

中綴表達式轉逆波蘭表達式

這裡使用栗子：

（1 + 2 * (4 - 3) + 6/2）

算法僞代碼（如果不清楚流程的話，務必要先看一下）

輸入：中綴表達式串

輸出：字尾表達式串

PROCESS BEGIN:

   1.從左往右掃描中綴表達式串s，對于每一個操作數或操作符，執行以下操作;

                2.IF (掃描到的s[i]是操作數DATA)

　　　　　    将s[i]添加到輸出隊列中;

               3.IF (掃描到的s[i]是開括号'(')

                        将s[i]壓棧;

               4.WHILE (掃描到的s[i]是操作符OP)

                       IF (棧為空 或 棧頂為'(' 或 掃描到的操作符優先級比棧頂操作符高)

                             将s[i]壓棧;

                             BREAK;

                       ELSE

                             出棧至輸出隊列中

               5.IF (掃描到的s[i]是閉括号')')

                       棧中運算符逐個出棧并輸出，直到遇到開括号'(';

                       開括号'('出棧并丢棄;

               6.傳回第1.步

　　       7.WHILE (掃描結束而棧中還有操作符)

                        操作符出棧并加到輸出隊列中

PROCESS END           

複制

是以将上面的栗子放進去走一圈出來會怎樣？

in>>（1 + 2 (4 - 3) + 6/2）

out<<1 2 4 3 -+ 6 2 / +

了解流程之後，我們來看個表：對于上面的栗子的轉換

在這裡插入圖檔描述

字尾表達式運算流程

逆波蘭表達式的計算就比較簡單了。以上面結果中的隊列為輸入，同時再準備一個棧用于運算。具體流程如下：

• 将隊列中的資料依次出隊，然後壓棧；
• 在出隊的過程中如果遇到運算符，則從棧中彈出2個運算數，分别作為右運算數和左運算數，進行運算；
• 将步驟2的運算結果入棧；
• 跳入步驟1，繼續進行出隊操作。

對上面栗子進行流程化：

①

在這裡插入圖檔描述

②

在這裡插入圖檔描述

③

在這裡插入圖檔描述

我講清楚了嗎？

放碼過去

這是一個多項式電腦的代碼，注釋我就沒放（危險動作，請勿模仿）。

#ifndef _STACK_H_
#define _STACK_H_

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

#define SIZE 10

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

typedef struct stack
{
    Node *top;
}Stack;

void Init(Stack *s);

int Empty(Stack *s);

void Push(Stack *s, int data);

void Pop(Stack *s);

int GetTop(Stack *s);

#endif            

複制

#include "stack.h"


void Init(Stack *s)
{
    if (NULL == s)
        return;

    s->top = NULL;
}

int Empty(Stack *s)
{
    if (NULL == s)
        return 0;

    if (NULL == s->top)
        return 1;

    return 0;
}

void Push(Stack *s,int data)
{
    if (NULL == s)
        return;

    Node *node = (Node *)malloc(sizeof(Node)/sizeof(char));
    if (NULL == node)
        return;

    node->data = data;
    node->next = s->top;
    s->top = node;
}

void Pop(Stack *s)
{
    if (NULL == s)
        return;

    if (Empty(s) == 1)
        return;

    Node *tmp = s->top;
    s->top = tmp->next;
    free(tmp);
}

int GetTop(Stack *s)
{
    if (NULL == s)
        return;

    if (Empty(s) == 1)
    {
        printf ("無棧頂元素\n");
        exit(-1); 
    }

    return s->top->data;
}           

複制

#include <stdio.h>
#include "stack.h"
#include <string.h>

int Ope_judge(Stack *s_ope,int ope)
{
    if(Empty(s_ope))
        return 1;

    int top = GetTop(s_ope);

    switch(top)
    {
        case '+':
        case '-':
            if(ope == '*' || ope == '/' || ope == '(')
                return 1;
            break;
        case '*':
        case '/':
            if( ope == '(')
                return 1;
            break;
        case '(':
            if(ope == ')')
            {
                Pop(s_ope);
            }
            return 1;
        default :
            break;
    }

    return 0;
}

void Calc(Stack *s_ope,Stack *s_num)
{
    int num1 = GetTop(s_num);
    Pop(s_num);

    int num2 = GetTop(s_num);
    Pop(s_num);

    int ope = GetTop(s_ope);
    Pop(s_ope);

    int res;
    switch(ope)
    {
        case '+':
            res = num2 + num1;
            break;
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num2 * num1;
            break;
        case '/':
            res = num2 / num1;
            break;
        default:
            break;
    }
    Push(s_num,res);
}


void Ope_deal(Stack *s_ope,Stack *s_num,int ope)
{
    if(Ope_judge(s_ope,ope) == 1)
    {
        Push(s_ope,ope);
    }
    else
    {
        while(Ope_judge(s_ope,ope) == 0)
        {
            Calc(s_ope,s_num);
        }

        if(ope != ')')
            Push(s_ope,ope);
    }

}

int main()
{
    char buf[100];
    fgets(buf,100,stdin);
    buf[strlen(buf)-1] = '\0';

    Stack s_num;
    Stack s_ope;

    Init (&s_num);
    Init (&s_ope);

    char *p = buf;
    while(*p)
    {
        if(*p >= '0' && *p <= '9')
        {
            int num = 0;
            while(*p >= '0' && *p <= '9')
            {
                num = num *10 + *p - '0';
                p++;
            }

            Push(&s_num , num);
            continue;
        }
        Ope_deal(&s_ope,&s_num,*p);
        p++;
    }

        while(!Empty(&s_ope))
        {
            Calc(&s_ope,&s_num);
        }

        int res = GetTop(&s_num);

        printf ("計算結果為：%d\n", res);


    return 0;
}           

複制

在這裡插入圖檔描述

隊列

關于隊列，就真的不知道該再說啥了。上邊的棧已經說得天花亂墜了。

但是隊列在後端開發又占有不低的地位，為啥，消息隊列如果沒聽過，卡夫卡聽過嗎？

RocketMQ沒聽過，雙十一剁手剁過嗎？沒有消息隊列，各位怎麼能愉快的雙十一搶購呢。

隊列是一種先進先出(FIFO) 的線性表。在表一端插入，在另一端删除。

在這裡插入圖檔描述

在這裡插入圖檔描述

消息隊列

想要進一步了解隊列的小夥伴請移步：

消息隊列：解耦、異步、削峰，現有MQ對比以及新手入門該如何選擇MQ?