堆疊
定義:
堆疊(Stack),是運算受限的線性表,插入和取出操作都只能在表頭進行,也稱之為后進先出(LIFO)線性表;
案例:
有名為stk的堆疊,按順序插入:1,2,3三個元素,插入完成后取出全部,順序為:3,2,1;
堆疊的實作:
既然是線性表,則可以通過順序結構和鏈接結構來實作,通過順序結構實作的堆疊稱為順序堆疊,通過鏈接結構實作的堆疊稱為鏈堆疊;
常用操作:
- 初始化
- 入堆疊
- 出堆疊
- 取堆疊頂元素
- 空堆疊判斷
使用場景:
程式中函式(方法)的執行通常都是借助堆疊來完成的,當要執行一個函式時,會將函式代碼壓入堆疊中,執行完畢則出堆疊,執行程序中若呼叫了其他函式,則被調函式同樣會入堆疊,所以程式中的函式嵌套呼叫時,也是遵循后進先出;
順序實作
順序堆疊資料結構:
c語言實作:
#include <stdio.h>
//堆疊的順序實作
//定義資料結構
const int SIZE = 5;
typedef struct{
int data[SIZE];
int top;
}seqStk,*SEQStack;
SEQStack initalStack(){
SEQStack stack = malloc(sizeof(seqStk));
stack->top = -1;
return stack;
}
int isEmpty(SEQStack stack){
if(stack->top == -1){
return 1;
}
return 0;
}
int getTop(SEQStack stack){
if (isEmpty(stack)) {
printf("err:stack is empty!\n");
return NULL;
}else{
return stack->data[stack->top];
}
}
int pop(SEQStack stack){
//先進后出,出堆疊是判斷是否空
if (isEmpty(stack)) {
printf("err:stack is empty!\n");
return NULL;
}else{
int temp = getTop(stack);
stack->top--;
return temp;
}
}
void push(SEQStack stack,int data){
if (stack->top == SIZE-1) {
printf("err:stack already full!\n");
}else{
stack->top++;
stack->data[stack->top] = data;
}
}
int main(int argc, const char * argv[]) {
SEQStack stack = initalStack();
push(stack,100);
push(stack,200);
push(stack,300);
push(stack,400);
push(stack,500);
push(stack,600);
printf("geted:%d\n",pop(stack));
printf("geted:%d\n",getTop(stack));
printf("geted:%d\n",pop(stack));
printf("geted:%d\n",pop(stack));
printf("geted:%d\n",pop(stack));
printf("geted:%d\n",pop(stack));
printf("Hello, World!\n");
return 0;
}
雙堆疊
順序實作的弊端就在于,無法預估資料長度,會造成空間浪費,為了避免這個問題,我們可以讓兩個堆疊共享同一個順序存盤空間,起始地址和結束地址分別作為兩個堆疊的堆疊底;
- 資料結構及相關操作:
鏈接實作
資料結構:
c語言實作:
#include <stdio.h>
//結構定義
typedef struct node{
int data;
struct node *next;
}Node,*LinkStk;
LinkStk initialStack(){
LinkStk stack = malloc(sizeof(Node));
stack->next = NULL;
return stack;
}
int isEmpty(LinkStk stack){
if (stack->next == NULL) {
return 1;
}
return 0;
}
void push(LinkStk stack,int data){
Node *p = malloc(sizeof(Node));
p->next = stack->next;
p->data = https://www.cnblogs.com/yangyuanhu/p/data;
stack->next = p;
}
Node *getTop(LinkStk stack){
return stack->next;
}
void *pop(LinkStk stack){
if (isEmpty(stack)) {
printf("error:stack is empty!\n");
return NULL;
}
Node *temp = stack->next;
stack->next = temp->next;
free(temp);
}
int main(int argc, const char * argv[]) {
LinkStk stack = initialStack();
push(stack, 100);
push(stack, 200);
push(stack, 300);
pop(stack);
pop(stack);
pop(stack);
Node *a = getTop(stack);
if (a != NULL){
printf("%d\n",a->data);
}
push(stack, 900);
Node *w = getTop(stack);
printf("%d\n",w->data);
printf("Hello, World!\n");
return 0;
}
案例中所有操作演算法時間復雜度均為O(1);
佇列
定義:
佇列(Queue),同堆疊相同,也是運算受限的線性表,其插入只能在表未進行,而洗掉只能在表頭進行,稱之為先進先出(FIFO)線性表;
案例:
有名為stk的堆疊,按順序插入:1,2,3三個元素,插入完成后取出全部,順序為:1,2,3;
佇列的實作:
既然是線性表,同樣也可以通過順序結構和鏈接結構來實作;
常用操作:
- 初始化
- 入佇列
- 出佇列
- 取佇列首元素
- 空佇列判斷
使用場景:
佇列的核心就在于,先來先得,先進佇列的一定先出,這非常適合用在需要保證處理順序的業務上,例如秒殺活動;
順序實作
佇列中的元素是具有順序的所以可通過順序結構實作,常見的方式就是通過陣列,但是陣列的問題是無法準確預估元素大小
此外,當有元素從佇列中出去時,佇列則可以存如儲新的元素,但是心存盤的元素應該放在那里卻成了一個問題,
實作原理簡述:
c語言實作:
#include <stdio.h>
const int max_size = 5;
//資料結構定義
typedef struct LQueue{
int data[max_size];
int front;
int rear;
}LQueue,*Queue;
//初始化
LQueue *initial(){
LQueue *queue = malloc(sizeof(LQueue));
queue->front = 0;
queue->rear = 0;
return queue;
}
//入佇列
void put(LQueue *queue,int data){
if ((queue->rear+1)%max_size == queue->front){
printf("error:佇列已滿\n");
exit(-1);
} else{
queue->rear = (queue->rear+1)%max_size;
queue->data[queue->rear] = data;
}
}
//判空
int isEmpty(LQueue *queue){
return queue->rear == queue->front;
}
//出佇列
int get(LQueue *queue){
if (isEmpty(queue)){
printf("error:佇列為空");
exit(-1);
}else{
queue->front = (queue->front+1)%max_size;
return queue->data[queue->front];
}
}
//測驗
int main(int argc, const char * argv[]) {
Queue queue = initial();
put(queue,1);
put(queue,2);
put(queue,3);
put(queue,4);
printf("%d\n",get(queue));
printf("%d\n",get(queue));
put(queue,5);
put(queue,6);
printf("%d\n",get(queue));
printf("%d\n",get(queue));
printf("%d\n",get(queue));
printf("%d\n",get(queue));
put(queue,7);
printf("%d\n",get(queue));
printf("Hello, World!\n");
return 0;
}
```
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198923.html
標籤：其他
上一篇：資料結構之堆疊—強大的四則復雜運算計算器(媲美windows自帶的科學計算器)【中綴轉后綴運算式】
下一篇：資料結構（C語言版）---堆疊