數(shù)據(jù)結(jié)構(gòu)與算法篇-隊列實現(xiàn)棧
01
—
隊列實現(xiàn)棧原理簡述
棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu)，而隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，兩者原理不難理解，使用也簡單。但是我們不僅僅要掌握數(shù)據(jù)結(jié)構(gòu)的基本原理，還要學會靈活運用，能否靈活運用是考察一個人對數(shù)據(jù)結(jié)構(gòu)的理解程度，也是在面試的時候經(jīng)常會考到的知識點?，F(xiàn)在假設面試官要求你用隊列實現(xiàn)棧，你的解決方案是什么？通過棧的基本原理我們知道，只要每次進行stack_pop操作時將隊列里最后一個元素輸出就能模擬棧的輸出操作。
—
隊列實現(xiàn)棧方案和實現(xiàn)
我們很容易想到一種解決方案，隊列queue1保存原始輸入數(shù)據(jù)，隊列queue2作為臨時隊列緩存數(shù)據(jù)，只要進行stack_pop操作時，先將queue1里除最后一個元素外全部出隊，且出隊的數(shù)據(jù)保存在一個臨時隊列queue2里，保存queue1最后的元素，最后再將queue2里的全部元素出隊，且出隊的元素重新放進queue1里，返回保存的queue1最后的元素。
我們作了下圖便于理解2個隊列模擬棧的過程。
一個棧輸出元素順序
在數(shù)據(jù)結(jié)構(gòu)與算法篇-隊列和數(shù)據(jù)結(jié)構(gòu)與算法篇-棧文章里我們詳細介紹了隊列和棧的原理，并都用C實現(xiàn)了隊列和棧?，F(xiàn)在我們復用這兩篇文章里隊列的實現(xiàn)代碼，用于實現(xiàn)棧。定義棧相關(guān)數(shù)據(jù)結(jié)構(gòu)和操作函數(shù)代碼如下：
typedef struct stack{
queue_arr_t queue1;
queue_arr_t queue2;
}_stack_t;
extern void stack_init(_stack_t *s, int cap);
extern void stack_destroy(_stack_t *s);
extern void stack_push(_stack_t *s, int data);
extern int stack_pop(_stack_t *);
extern int stack_pop2(_stack_t *s);
extern bool stack_is_empty(_stack_t *s);
extern bool stack_is_full(_stack_t *s);棧初始化函數(shù)實現(xiàn)：
void stack_init(_stack_t *s, int cap){
if(s == NULL || cap <= 0){
return;
}
queue_arr_init(&s->queue1, cap);
queue_arr_init(&s->queue2, cap);
}棧銷毀函數(shù)實現(xiàn)：
void stack_destroy(_stack_t *s){
if(s == NULL){
return;
}
queue_arr_destroy(&s->queue1);
queue_arr_destroy(&s->queue2);
}入棧函數(shù)實現(xiàn)：
void stack_push(_stack_t *s, int data){
if(s == NULL){
return;
}
enqueue_arr(&s->queue1, data);
}出棧函數(shù)實現(xiàn)：
int stack_pop(_stack_t *s){
if(s == NULL){
return NAN;
}
if(queue_arr_is_empty(&s->queue1)){
return NAN;
}
while(queue_arr_length(&s->queue1) > 1){
enqueue_arr(&s->queue2, dequeue_arr(&s->queue1));
}
int data = dequeue_arr(&s->queue1);
while(!queue_arr_is_empty(&s->queue2)){
enqueue_arr(&s->queue1, dequeue_arr(&s->queue2));
}
return data;
}判斷棧是否空和是否滿函數(shù)實現(xiàn)：
bool stack_is_empty(_stack_t *s){
if(s == NULL){
return true;
}
return queue_arr_is_empty(&s->queue1);
}
bool stack_is_full(_stack_t *s){
if(s == NULL){
return false;
}
return queue_arr_is_full(&s->queue1);
}
單個隊列模擬出棧函數(shù)實現(xiàn)如下：
int stack_pop2(_stack_t *s){
if(s == NULL){
return NAN;
}
if(queue_arr_is_empty(&s->queue1)){
return NAN;
}
int length = queue_arr_length(&s->queue1) - 1;
int data;
while(length--){
data = dequeue_arr(&s->queue1);
enqueue_arr(&s->queue1, data);
}
return dequeue_arr(&s->queue1);
}—
棧實現(xiàn)驗證
下面我們寫一個小程序驗棧實現(xiàn)的正確性。
#include <stdio.h>
#include "stack.h"
int main() {
int i = 0;
_stack_t my_stack;
stack_init(&my_stack, 5);
printf("入棧順序\n");
for(i = 0; i < 5; i++){
printf("%d ", i + 1);
stack_push(&my_stack, i + 1);
}
printf("\n");
printf("出棧順序\n");
for(i = 0; i < 5; i++){
printf("%d ", stack_pop(&my_stack));
}
printf("\n\n");
printf("優(yōu)化出棧操作\n");
printf("入棧順序\n");
for(i = 0; i < 5; i++){
printf("%d ", i + 1);
stack_push(&my_stack, i + 1);
}
printf("\n");
printf("出棧順序\n");
for(i = 0; i < 5; i++){
printf("%d ", stack_pop2(&my_stack));
}
printf("\n");
stack_destroy(&my_stack);
return 0;
}入棧順序
1 2 3 4 5
出棧順序
5 4 3 2 1
優(yōu)化出棧操作
入棧順序
1 2 3 4 5
出棧順序
5 4 3 2 1