【數據結構&演算法】08-棧概念&源碼
- 2021 年 11 月 5 日
- 筆記
- /label/dataStructure, /label/lzm, 書籍筆記, 博文, 教程集合, 數據結構, 數據結構與演算法, 演算法, 線性表
目錄
前言
李柱明部落格：//www.cnblogs.com/lizhuming/p/15487342.html
棧的定義
定義
棧（stack）是限定僅在表尾進行插入和刪除操作的線性表。
- 棧首先是一個線性表，棧元素具有線性關係。為特殊的線性表。
- 棧頂（top）：允許插入和刪除的一端稱為棧頂。
- 棧底（bottom）：另一端稱為棧底。
- 表尾指的是棧頂，而不是棧底。
- 空棧：不含任何數據元素的棧稱為空棧。
- LIFO：last in first out，棧又稱為後進先出的線性表，簡稱 LIFO 結構。
- 棧的插入操作：進棧，也稱壓棧、入棧。
- 棧的刪除操作：出棧，也稱彈棧。
- 用數組實現的棧叫做：順序棧
- 用鏈表實現的棧叫做：鏈式棧
小筆記：
-
記憶體中的堆棧和數據結構堆棧不是一個概念：
-
記憶體中的堆棧是真實存在的物理區。記憶體空間在邏輯上分為三部分：程式碼區、靜態數據區和動態數據區，動態數據區又分為棧區和堆區。
- 程式碼區 ：存儲方法體的二進位程式碼。高級調度（作業調度）、中級調度（記憶體調度）、低級調度（進程調度）控制程式碼區執行程式碼的切換。
- 靜態數據區 ：存儲全局變數、靜態變數、常量，常量包括 final 修飾的常量和 String 常量。系統自動分配和回收。
- 棧區 ：存儲運行方法的形參、局部變數、返回值。由系統自動分配和回收。例如 int method(int a){int b;}棧中存儲參數 a、局部變數 b、返回值 temp。
- 堆區 ：new 一個對象的引用或地址存儲在棧區，指向該對象存儲在堆區中的真實數據。由程式設計師分配和回收。
-
數據結構中的堆棧是抽象的數據存儲結構。
- 棧 ：是一種連續存儲的數據結構，特點是存儲的數據先進後出。
- 堆 ：是一棵完全二叉樹結構，特點是父節點的值大於（小於）兩個子節點的值（分別稱為大頂堆和小頂堆）。它常用於管理演算法執行過程中的資訊，應用場景包括堆排序，優先隊列等。
-
常見應用
棧相對於數組和鏈表來說只有限制，是操作受限的線性表。從功能上，數組和鏈表也可以代替棧，但是數組或鏈表暴露了太多的操作介面，操作上的確靈活自由，但使用時就比較不可控，自然也就更容易出錯。
棧的常見應用
- 軟體中的撤銷（undo）操作，瀏覽器歷史紀錄，Android 中的最近任務，Activity 的啟動模式，CPU 中棧的實現，Word 自動保存，解析計算式，解析 xml/json。
進棧出棧變化形式
出棧序列個數公式：卡特蘭公式：C(2n,n)/(n+1)
- n 為前幾個數時的值：1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 …
棧的抽象數據類型
棧為線性表，具備線性表的操作特性。
對於棧來說，插入和刪除改名為 push 和 pop。
- 壓
- 彈
棧的順序存儲結構及實現
棧的順序存儲結構
順序棧
- 棧的順序存儲也是線性表順序存儲的簡化，簡稱為順序棧。
- 在數組中，用下標為 0 的一段作為棧底。
- 棧頂 top：若存儲棧長度為 stack_size，則 top 必須少於 stack_size。
- 空棧：棧中有一個元素時，top=0。空棧時，top = -1。
順序棧的結構定義
- 指針式
// 指針式
typedef int se_type; /* 元素類型 */
typedef struct
{
se_type *top; /* 棧頂指針 */
se_type *bottom; /* 棧底指針 */
se_type stack_size; /* 棧的最大容量 */
}stack_t;
- 數組式
// 數組式
typedef int se_type; /* 元素類型 */
#define STACK_SIZE 100 /* 棧元素個數 */
typedef struct
{
int top; /* 棧頂指針 */
se_type data[STACK_SIZE]; /* 棧空間 */
}stack_t;
兩棧共享空間
兩棧共享空間：
-
原理：兩個棧底分別位於數組的始端（下標 0）和數組的末端（下標數組長度 n-1），增加元素即從兩端點向中間延伸。
-
條件：兩個具有相同數據類型的棧，生長方向相反。
-
滿棧判斷：
- 一般情況：兩個棧見面之時，即兩個指針相差 1，
top1+1 == top2時。 - 極端情況：stack_2 空時，top1=n-1，則 stack_1 滿；stack_1 空，top2=0，則 stack_2 滿。
- 一般情況：兩個棧見面之時，即兩個指針相差 1，
部分程式碼實現
// 數組式
/* 兩棧共享空間結構 */
typedef int se_type; /* 元素類型 */
#define STACK_SIZE 100 /* 棧元素個數 */
typedef struct
{
int top1; /* 棧頂指針 */
int top2; /* 棧頂指針 */
se_type data[STACK_SIZE]; /* 棧空間 */
}stack_double_t;
/**
* @name stack_double_creat
* @brief
* @param
* @retval
* @author lzm
*/
stack_double_t *stack_double_creat(void)
{
stack_t *stack_double_ptr = NULL;
stack_double_ptr = (stack_double_t *)malloc(sizeof(stack_double_t));
if(stack_double_ptr == NULL)
return NULL;
memset(stack_ptr, 0x00, sizeof(stack_double_t));
stack_double_ptr->top1 = -1;
stack_double_ptr->top2 = STACK_SIZE;
return stack_double_ptr;
}
/**
* @name stack_double_destroy
* @brief
* @param
* @retval
* @author lzm
*/
int stack_double_destroy(stack_double_t *stack)
{
if(stack != NULL)
{
free(stack);
return 0;
}
return -1;
}
棧的鏈式存儲結構及實現
棧的鏈式存儲結構
就是基於鏈表實現的棧。
棧的鏈式存儲結構：
- 棧的鏈式存儲結構，簡稱鏈棧。
- 棧頂放在單鏈表的頭部，且不需要頭結點。（自主決定）
- 空棧：鏈表原定義為頭指針指向空，故鏈棧的空是 top = NULL。
- 結構：
/* 鏈式結構 */
typedef int se_type; /* 元素類型 */
typedef struct stack_node
{
se_type date;
struct stack_node *next;
}stack_node_t;
typedef struct
{
int count;
stack_node_t *top;
}stack_link_t;
棧的應用之遞歸
遞歸的定義：
- 把一個直接調用自己或者通過一系列的調用語句間接地調用自己的函數，稱為遞歸函數。
- 每個遞歸定義必須至少有一個條件，滿足時遞歸不再進行，即不再引用自身而是返回值退出。（出口條件）
遞歸與棧結構：
- 遞歸進入時，壓棧。
- 遞歸退出時，出棧。
程式碼實現
指針式順序棧操作
/** @file stack.c
* @brief 簡要說明
* @details 詳細說明
* @author lzm
* @date 2021-09-06 09:42:22
* @version v1.0
* @copyright Copyright By lizhuming, All Rights Reserved
* @blog //www.cnblogs.com/lizhuming/
*
**********************************************************
* @LOG 修改日誌:
**********************************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 指針式
typedef int se_type; /* 元素類型 */
typedef struct
{
se_type *top; /* 棧頂指針 */
se_type *bottom; /* 棧底指針 */
se_type stack_size; /* 棧的最大容量，元素個數。 */
}stack_pointer_t;
/**
* @name stack_pointer_creat
* @brief
* @param
* @retval
* @author lzm
*/
stack_pointer_t *stack_pointer_creat(int size)
{
stack_pointer_t *stack_ptr = NULL;
stack_ptr = (stack_pointer_t *)malloc(sizeof(stack_pointer_t));
if(stack_ptr == NULL)
return NULL;
memset(stack_ptr, 0x00, sizeof(stack_pointer_t));
stack_ptr->bottom = (se_type *)malloc(size * sizeof(se_type));
if(stack_ptr->bottom == NULL)
{
free(stack_ptr);
return NULL;
}
memset(stack_ptr->bottom, 0x00, size * sizeof(se_type));
stack_ptr->top = stack_ptr->bottom;
stack_ptr->stack_size = size;
return stack_ptr;
}
/**
* @name stack_pointer_destroy
* @brief
* @param
* @retval
* @author lzm
*/
int stack_pointer_destroy(stack_pointer_t *stack)
{
if(stack != NULL)
{
if(stack->bottom != NULL)
free(stack->bottom);
free(stack);
return 0;
}
return -1;
}
/**
* @name stack_pointer_clear
* @brief
* @param
* @retval
* @author lzm
*/
int stack_pointer_clear(stack_pointer_t *stack)
{
if(stack == NULL)
return -1;
stack->top = stack->bottom;
return 0;
}
/**
* @name stack_pointer_empty
* @brief
* @param
* @retval
* @author lzm
*/
int stack_pointer_empty(stack_pointer_t *stack)
{
if(stack == NULL)
return -1;
if(stack->top == stack->bottom)
return 1;
return 0;
}
/**
* @name stack_pointer_full
* @brief
* @param
* @retval
* @author lzm
*/
int stack_pointer_full(stack_pointer_t *stack)
{
if(stack == NULL)
return -1;
if(stack->top == (stack->bottom + stack->stack_size * sizeof(se_type)))
return 1;
return 0;
}
/**
* @name stack_pointer_length
* @brief
* @param
* @retval
* @author lzm
*/
int stack_pointer_length(stack_pointer_t *stack)
{
if(stack == NULL)
return -1;
return (stack->top - stack->bottom)/sizeof(se_type);
}
/**
* @name stack_pointer_push
* @brief
* @param
* @retval
* @author lzm
*/
int stack_pointer_push(stack_pointer_t *stack, se_type elem)
{
if(stack_pointer_full(stack) != 0)
return -1;
*stack->top = elem;
stack->top += sizeof(se_type);
return 0;
}
/**
* @name stack_pointer_pop
* @brief
* @param
* @retval
* @author lzm
*/
int stack_pointer_pop(stack_pointer_t *stack, se_type *elem)
{
if(stack_pointer_empty(stack) != 0)
{
elem = NULL;
return -1;
}
stack->top -= sizeof(se_type);
elem = stack->top;
return 0;
}
int main(void)
{
;
}
數組式順序棧操作
/** @file stack.c
* @brief 簡要說明
* @details 詳細說明
* @author lzm
* @date 2021-09-06 09:42:22
* @version v1.0
* @copyright Copyright By lizhuming, All Rights Reserved
* @blog //www.cnblogs.com/lizhuming/
*
**********************************************************
* @LOG 修改日誌:
**********************************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 數組式
typedef int se_type; /* 元素類型 */
#define STACK_SIZE 100 /* 棧元素個數 */
typedef struct
{
int top; /* 棧頂指針 */
se_type data[STACK_SIZE]; /* 棧空間 */
}stack_t;
/**
* @name stack_creat
* @brief
* @param
* @retval
* @author lzm
*/
stack_t *stack_array_creat(void)
{
stack_t *stack_ptr = NULL;
stack_ptr = (stack_t *)malloc(sizeof(stack_t));
if(stack_ptr == NULL)
return NULL;
memset(stack_ptr, 0x00, sizeof(stack_t));
stack_ptr->top = -1;
return stack_ptr;
}
/**
* @name stack_destroy
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_destroy(stack_t *stack)
{
if(stack != NULL)
{
free(stack);
return 0;
}
return -1;
}
/**
* @name stack_clear
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_clear(stack_t *stack)
{
if(stack == NULL)
return -1;
stack->top = -1;
return 0;
}
/**
* @name stack_empty
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_empty(stack_t *stack)
{
if(stack == NULL)
return -1;
if(stack->top == -1)
return 1;
return 0;
}
/**
* @name stack_full
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_full(stack_t *stack)
{
if(stack == NULL)
return -1;
if(stack->top == STACK_SIZE-1)
return 1;
return 0;
}
/**
* @name stack_length
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_length(stack_t *stack)
{
if(stack == NULL)
return -1;
return stack->top + 1;
}
/**
* @name stack_push
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_push(stack_t *stack, se_type elem)
{
if(stack_array_full(stack) != 0)
return -1;
stack->top++;
stack->data[stack->top] = elem;
return 0;
}
/**
* @name stack_pop
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_pop(stack_t *stack, se_type *elem)
{
if(stack_array_empty(stack) != 0 || elem == NULL)
{
return -1;
}
*elem = stack->data[stack->top];
stack->top--;
return 0;
}
/**
* @name stack_get_top
* @brief
* @param
* @retval
* @author lzm
*/
int stack_array_get_top(stack_t *stack, se_type *elem)
{
if(stack_array_empty(stack) != 0 || elem == NULL || stack->top >= STACK_SIZE)
{
return -1;
}
*elem = stack->data[stack->top];
return 0;
}
鏈式棧
/** @file stack.c
* @brief 簡要說明
* @details 詳細說明
* @author lzm
* @date 2021-09-06 22:52:12
* @version v1.0
* @copyright Copyright By lizhuming, All Rights Reserved
* @blog //www.cnblogs.com/lizhuming/
*
**********************************************************
* @LOG 修改日誌:
**********************************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 鏈式結構 */
typedef int se_type; /* 元素類型 */
typedef struct stack_node
{
se_type date;
struct stack_node *next;
}stack_node_t;
typedef struct
{
int count;
stack_node_t *top;
}stack_link_t;
/**
* @name stack_link_creat
* @brief
* @param
* @retval
* @author lzm
*/
stack_link_t *stack_creat(int size)
{
stack_link_t *stack_ptr = NULL;
stack_ptr = (stack_link_t *)malloc(sizeof(stack_link_t));
if(stack_ptr == NULL)
return NULL;
memset(stack_ptr, 0x00, sizeof(stack_link_t));
stack_ptr->count = 0;
stack_ptr->top = NULL;
return stack_ptr;
}
/**
* @name stack_link_destroy
* @brief
* @param
* @retval
* @author lzm
*/
int stack_link_destroy(stack_link_t *stack)
{
stack_node_t *stack_cur = NULL;
stack_node_t *stack_last = NULL;
if(stack == NULL)
return -1;
stack_cur = stack->top;
while(stack_cur)
{
stack_last = stack_cur;
stack_cur = stack_cur->next;
free(stack_last);
}
free(stack);
return 0;
}
/**
* @name stack_link_clear
* @brief
* @param
* @retval
* @author lzm
*/
int stack_link_clear(stack_link_t *stack)
{
stack_node_t *stack_cur = NULL;
stack_node_t *stack_last = NULL;
if(stack == NULL)
return -1;
stack_cur = stack->top;
while(stack_cur)
{
stack_last = stack_cur;
stack_cur = stack_cur->next;
free(stack_last);
}
return 0;
}
/**
* @name stack_link_empty
* @brief
* @param
* @retval
* @author lzm
*/
int stack_link_empty(stack_link_t *stack)
{
if(stack == NULL)
return -1;
if(stack->count == 0)
return 1;
return 0;
}
/**
* @name stack_link_length
* @brief
* @param
* @retval
* @author lzm
*/
int stack_link_length(stack_link_t *stack)
{
if(stack == NULL)
return -1;
return (stack->count);
}
/**
* @name stack_link_push
* @brief
* @param
* @retval
* @author lzm
*/
int stack_link_push(stack_link_t *stack, se_type elem)
{
stack_node_t *stack_node_ptr = NULL;
stack_node_ptr = (stack_node_t *)malloc(sizeof(stack_node_t));
if(stack_node_ptr == NULL)
return -1;
memset(stack_node_ptr, 0x00, sizeof(stack_node_t));
stack_node_ptr->date = elem;
stack_node_ptr->next = stack->top;
stack->top = stack_node_ptr->next;
stack->count++;
return 0;
}
/**
* @name stack_link_pop
* @brief
* @param
* @retval
* @author lzm
*/
int stack_link_pop(stack_link_t *stack, se_type *elem)
{
stack_node_t *node = NULL;
if(stack_link_empty(stack) != 0 || elem == NULL)
{
return -1;
}
*elem = stack->top->date;
node = stack->top;
stack->top = stack->top->next;
free(node);
stack->count--;
return 0;
}
/**
* @name stack_link_get_top
* @brief
* @param
* @retval
* @author lzm
*/
int stack_link_get_top(stack_link_t *stack, se_type *elem)
{
if(stack_link_empty(stack) != 0 || elem == NULL)
{
return -1;
}
*elem = stack->top->date;
return 0;
}
