溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天小編給大家分享一下C++數據結構的棧與隊列實例分析的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端 稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。
棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的 代價比較小。
Stack.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int bool;
#define TRUE 1;
#define FALSE 0;
typedef int STDataType;
struct Stack
{
STDataType* a;
int top; //棧頂
int capacity; //容量，方便增容
};
//typedef struct Stack ST;
typedef struct Stack Stack;
//初始化
void StackInit(Stack* pst);
//銷毀
void StackDestroy(Stack* pst);
//入棧
void StackPush(Stack* pst, STDataType x);
//出棧
void StackPop(Stack* pst);
//返回棧頂數據
STDataType StackTop(Stack* pst);
//判斷棧是否為空,空返回1非空返回0
//int StackEmpty(Stack* pst);
bool StackEmpty(Stack* pst);
//棧中數據個數
int StackSize(Stack* pst);Stack.c
#include "Stack.h"
//初始化
void StackInit(Stack* pst)
{
assert(pst);
/*pst->a = NULL;
pst->top = 0;
pst->capacity = 0;*/
//開始就申請空間，好處在于空間不夠時直接容量*2即可(如果剛開始是0就要單獨處理)
pst->a = malloc(sizeof(STDataType) * 4);
pst->top = 0;
pst->capacity = 4;
}
//銷毀
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
//入棧
void StackPush(Stack* pst, STDataType x)
{
assert(pst);
//從top為0的位置開始放
//如果滿了就增容
if (pst->top == pst->capacity)
{
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
if (tmp == NULL)
{
//如果開辟空間失敗
printf("realloc fail\n");
exit(-1);//結束整個程序(-1表示異常退出)
}
pst->a = tmp;
pst->capacity *= 2;
}
//入數據
pst->a[pst->top] = x;
pst->top++;
}
//出棧
void StackPop(Stack* pst)
{
assert(pst);//不能是空指針
assert(!StackEmpty(pst)); //棧內還有元素才能出戰
pst->top--;
}
//返回棧頂數據
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];
}
//判斷棧是否為空,空返回1非空返回0
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
int StackSize(Stack* pst)
{
assert(pst);
return pst->top;
}test.c
#include "Stack.h"
//對棧操作的測試
void TestStack()
{
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
//棧遍歷數據
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
//4 3 2 1
StackDestroy(&st);
}
int main()
{
TestStack();
return 0;
}隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出 FIFO(First In First Out)
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int QDataType;
//隊列中的一個結點
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
//隊列(由于需要兩個指針，所以用結構體定義)
typedef struct Queue
{
QueueNode* head; //頭指針
QueueNode* tail; //尾指針
}Queue;
//初始化
void QueueInit(Queue* pq);
//銷毀
void QueueDestroy(Queue* pq);
//入隊
void QueuePush(Queue* pq, QDataType x);
//出隊
void QueuePop(Queue* pq);
//取隊頭數據
QDataType QueueFront(Queue* pq);
//取隊尾數據
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//計算隊列元素個數
int QueueSize(Queue* pq);Queue.c
#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
//不帶哨兵位
pq->head = pq->tail = NULL;
}
//銷毀
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL; //等于空就為真, 不為空就是假
}
//入隊
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)//申請空間失敗
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//出隊
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));//空隊列也不能調用出隊操作
if (pq->head->next == NULL)//只有一個結點的情況(如果不單獨考慮，那當只有一個結點時，tail會仍然指向曾經的隊尾)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//取隊頭數據
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//取隊尾數據
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
int size = 0;
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}test.c
#include "Queue.h"
//對隊列操作的測試
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
printf("%d\n", QueueSize(&q)); //4
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
//1 2 3 4
QueueDestroy(&q);
}
int main()
{
TestQueue();
return 0;
}bool isValid(char * s)
{
Stack st;
StackInit(&st);
while(*s)
{
//左括號入棧，右括號找最近的左括號匹配
if(*s == '[' || *s == '(' || *s == '{')
{
StackPush(&st, *s);
s++;
}
else
{
if(StackEmpty(&st))//只有后括號的情況
{
StackDestroy(&st);
return false;
}
char top = StackTop(&st);
//不匹配的情況
if ( (top == '[' && *s != ']')
|| (top == '(' && *s != ')')
|| (top == '{' && *s != '}') )
{
StackDestroy(&st);
return false;
}
else //匹配的情況
{
StackPop(&st);
s++;
}
}
}
//如果最后棧內為空才說明是匹配的(防止最后棧內還剩下前括號的情況)
bool ret = StackEmpty(&st);
StackDestroy(&st);
return ret;
//特別注意:在return之前需要先把棧銷毀掉
}//思路:
//入棧: 向不為空的隊列入數據,始終保持另一個隊列為空
//出棧: 前size-1個數據導入空隊列，刪除最后一個
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
//*為什么下面代碼傳參都要傳&obj->q1/q2？
//因為應該傳入函數中的是隊列的指針
MyStack* myStackCreate()
{
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x)
{
//往不為空的隊列里入數據
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj)
{
//假設q1為空q2不為空
Queue* pEmpty = &obj->q1;
Queue* pNonEmpty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
pEmpty = &obj->q2;
pNonEmpty = &obj->q1;
}
//取出前size-1個插入空隊列
while(QueueSize(pNonEmpty) > 1)
{
QueuePush(pEmpty, QueueFront(pNonEmpty));
QueuePop(pNonEmpty);
}
//"干掉"最后一個
int front = QueueBack(pNonEmpty);
QueuePop(pNonEmpty);
return front;
}
int myStackTop(MyStack* obj)
{
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
//先釋放兩個隊列，再釋放malloc出來的結構體
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}typedef struct
{
Stack pushST;
Stack popST;
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&q->pushST);
StackInit(&q->popST);
return q;
}
void myQueuePush(MyQueue* obj, int x)
{
//不管棧內有沒有數據，只要是入隊操作就向Push棧入數據即可
StackPush(&obj->pushST, x);
}
//獲取隊頭數據
int myQueuePeek(MyQueue* obj)
{
//如果pop棧為空,先把push棧數據導入pop棧
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
return StackTop(&obj->popST);
}
//出隊
int myQueuePop(MyQueue* obj)
{
//如果pop棧為空,先把push棧數據導入pop棧
/*if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
*/
//復用
int top = myQueuePeek(obj);//易錯點:不能寫&obj->popST,因為該傳入隊列的指針
StackPop(&obj->popST);
return top;
}
bool myQueueEmpty(MyQueue* obj)
{
//push棧和pop棧同時為空,隊列才為空
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj)
{
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}題目描述：
設計你的循環隊列實現。 循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為“環形緩沖器”。
循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能使用這些空間去存儲新的值。
你的實現應該支持如下操作：
MyCircularQueue(k): 構造器，設置隊列長度為 k 。
Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
enQueue(value): 向循環隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環隊列是否為空。
isFull(): 檢查循環隊列是否已滿。
//循環隊列是邏輯上的循環(數組、鏈表都可以實現,本題使用數組)
//永遠空出一個位置不存儲數據(目的是區分空和滿)
//當front = tail說明循環隊列空
//當tail+1 = front說明循環隊列滿
typedef struct
{
int* a; //數組
int k; //循環隊列最多能存多少個數據
int front; //頭指針
int tail; //尾指針(隊尾數據的下一個位置)
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int)*(k+1)); //需要多開一個空間
obj->front = 0;
obj->tail = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
int tailNext = obj->tail + 1;
if(tailNext == obj->k+1)
{
//如果tail已經走到尾(不存放數據的位置),此時認為tailNext回到了數組首元素位置
tailNext = 0;
}
return tailNext == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
obj->tail++;
if(obj->tail == obj->k+1) //也可以取模
{
obj->tail = 0;
}
/* //取模
obj->tail %= (obj->k+1);
*/
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))//如果obj為空了就不能出數據
{
return false;
}
else
{
obj->front++;
//極端情況:front加到尾后重新回到數組首元素
if(obj->front == obj->k+1)
{
obj->front = 0;
}
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
//由于取尾需要去tail的前一個,那么當tail就在首元素的時候,要把它挪到最后一個元素的位置去
int tailPrev = obj->tail - 1;
if(tailPrev == -1)
{
tailPrev = obj->k;
}
return obj->a[tailPrev];
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}以上就是“C++數據結構的棧與隊列實例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
