當前位置: 首頁 社區 >淺談算法和數據結構: 一 棧和隊列

淺談算法和數據結構: 一 棧和隊列

算法文摘2021-05-06 14:47:56

戳上面的藍字關注我們哦!


本文作者:yangecnu

地址:http://www.cnblogs.com/yangecnu

最近晚上在家里看Algorithems,4th Edition,我買的英文版,覺得這本書寫的比較淺顯易懂,而且“圖碼并茂”,趁著這次機會打算好好學習做做筆記,這樣也會印象深刻,這也是寫這一系列文章的原因。另外普林斯頓大學在Coursera?上也有這本書同步的公開課,還有另外一門算法分析課,這門課程的作者也是這本書的作者,兩門課都挺不錯的。

計算機程序離不開算法和數據結構,本文簡單介紹棧(Stack)和隊列(Queue)的實現,.NET中與之相關的數據結構,典型應用等,希望能加深自己對這兩個簡單數據結構的理解。

1.?基本概念

概念很簡單,棧 (Stack)是一種后進先出(last in first off,LIFO)的數據結構,而隊列(Queue)則是一種先進先出 (fisrt in first out,FIFO)的結構,如下圖:

2.?實現

現在來看如何實現以上的兩個數據結構。在動手之前,Framework Design Guidelines這本書告訴我們,在設計API或者實體類的時候,應當圍繞場景編寫API規格說明書。

1.1?Stack的實現

棧是一種后進先出的數據結構,對于Stack 我們希望至少要對外提供以下幾個方法:

Stack<T>()

創建一個空的棧

void Push(T s)

往棧中添加一個新的元素

T Pop()

移除并返回最近添加的元素

boolean IsEmpty()

棧是否為空

int Size()

棧中元素的個數

要實現這些功能,我們有兩中方法,數組和鏈表,先看鏈表實現:

棧的鏈表實現:

我們首先定義一個內部類來保存每個鏈表的節點,該節點包括當前的值以及指向下一個的值,然后建立一個節點保存位于棧頂的值以及記錄棧的元素個數;

class Node
{
? ?public T Item{get;set;}
? ?public Node Next { get; set; }
}
private Node first = null;
private int number = 0;

現在來實現Push方法,即向棧頂壓入一個元素,首先保存原先的位于棧頂的元素,然后新建一個新的棧頂元素,然后將該元素的下一個指向原先的棧頂元素。整個Pop過程如下:

實現代碼如下:

void Push(T node)
{
? ?Node oldFirst = first;
? ?first = new Node();
? ?first.Item= node;
? ?first.Next = oldFirst;
? ?number++;
}

Pop方法也很簡單,首先保存棧頂元素的值,然后將棧頂元素設置為下一個元素:

T Pop()
{
? ?T item = first.Item;
? ?first = first.Next;
? ?number--;
? ?return item;
}

基于鏈表的Stack實現,在最壞的情況下只需要常量的時間來進行Push和Pop操作。

棧的數組實現:

我們可以使用數組來存儲棧中的元素Push的時候,直接添加一個元素S[N]到數組中,Pop的時候直接返回S[N-1].

首先,我們定義一個數組,然后在構造函數中給定初始化大小,Push方法實現如下,就是集合里添加一個元素:

T[] item;
int number = 0;

public StackImplementByArray(int capacity)
{
? ?item = new T[capacity];
}
public void Push(T _item)
{
? ?if (number == item.Length) Resize(2 * item.Length);
? ?item[number++] = _item;
}

Pop方法:

public T Pop()
{
? ?T temp = item[--number];
? ?item[number] = default(T);
? ?if (number > 0 && number == item.Length / 4) Resize(item.Length / 2);
? ?return temp;
}

在Push和Pop方法中,為了節省內存空間,我們會對數組進行整理。Push的時候,當元素的個數達到數組的Capacity的時候,我們開辟2倍于當前元素的新數組,然后將原數組中的元素拷貝到新數組中。Pop的時候,當元素的個數小于當前容量的1/4的時候,我們將原數組的大小容量減少1/2。

Resize方法基本就是數組復制:

private void Resize(int capacity)
{
? ?T[] temp = new T[capacity];
? ?for (int i = 0; i < item.Length; i++)
? ?{
? ? ? ?temp[i] = item[i];
? ?}
? ?item = temp;
}

當我們縮小數組的時候,采用的是判斷1/4的情況,這樣效率要比1/2要高,因為可以有效避免在1/2附件插入,刪除,插入,刪除,從而頻繁的擴大和縮小數組的情況。下圖展示了在插入和刪除的情況下數組中的元素以及數組大小的變化情況:

分析:1. Pop和Push操作在最壞的情況下與元素個數成比例的N的時間,時間主要花費在擴大或者縮小數組的個數時,數組拷貝上。

2. 元素在內存中分布緊湊,密度高,便于利用內存的時間和空間局部性,便于CPU進行緩存,較LinkList內存占用小,效率高。

2.2 Queue的實現

Queue是一種先進先出的數據結構,和Stack一樣,他也有鏈表和數組兩種實現,理解了Stack的實現后,Queue的實現就比較簡單了。

Stack<T>()

創建一個空的隊列

void Enqueue(T s)

往隊列中添加一個新的元素

T Dequeue()

移除隊列中最早添加的元素

boolean IsEmpty()

隊列是否為空

int Size()

隊列中元素的個數


首先看鏈表的實現:

Dequeue方法就是返回鏈表中的第一個元素,這個和Stack中的Pop方法相似:

public T Dequeue()
{
? ?T temp = first.Item;
? ?first = first.Next;
? ?number--;
? ?if (IsEmpety())
? ? ? ?last = null;
? ?return temp;
}

Enqueue和Stack的Push方法不同,他是在鏈表的末尾增加新的元素:

public void Enqueue(T item)
{
? ?Node oldLast = last;
? ?last = new Node();
? ?last.Item = item;
? ?if (IsEmpety())
? ?{
? ? ? ?first = last;
? ?}
? ?else
? ?{
? ? ? ?oldLast.Next = last;
? ?}
? ?number++;
}

同樣地,現在再來看如何使用數組來實現Queue,首先我們使用數組來保存數據,并定義變量head和tail來記錄Queue的首尾元素。

和Stack的實現方式不同,在Queue中,我們定義了head和tail來記錄頭元素和尾元素。當enqueue的時候,tial加1,將元素放在尾部,當dequeue的時候,head減1,并返回。

public void Enqueue(T _item)
{
? ?if ((head - tail + 1) == item.Length) Resize(2 * item.Length);
? ?item[tail++] = _item;
}

public T Dequeue()
{
? ?T temp = item[--head];
? ?item[head] = default(T);
? ?if (head > 0 && (tail - head + 1) == item.Length / 4) Resize(item.Length / 2);
? ?return temp;
}

private void Resize(int capacity)
{
? ?T[] temp = new T[capacity];
? ?int index = 0;
? ?for (int i = head; i < tail; i++)
? ?{
? ? ? ?temp[++index] = item[i];
? ?}
? ?item = temp;
}

3.?.NET中的StackQueue

在.NET中有Stack和Queue泛型類,使用Reflector工具可以查看其具體實現。先看Stack的實現,下面是截取的部分代碼,僅列出了Push,Pop方法,其他的方法希望大家自己使用Reflector查看:

可以看到.NET中的Stack的實現和我們之前寫的差不多,也是使用數組來實現的。.NET中Stack的初始容量為4,在Push方法中,可以看到當元素個數達到數組長度時,擴充2倍容量,然后將原數組拷貝到新的數組中。Pop方法和我們之前實現的基本上相同,下面是具體代碼,只截取了部分:

[Serializable, ComVisible(false), 
DebuggerTypeProxy(typeof(System_StackDebugView<>)),
DebuggerDisplay("Count = {Count}"),
__DynamicallyInvokable]
public class Stack<T> :
? ? IEnumerable<T>, ICollection, IEnumerable
{
? ?// Fields
? ?private T[] _array;
? ?private const int _defaultCapacity = 4;
? ?private static T[] _emptyArray;
? ?private int _size;
? ?private int _version;

? ?// Methods
? ?static Stack()
? ?
{
? ? ? ?Stack<T>._emptyArray = new T[0];
? ?}

? ?[__DynamicallyInvokable]
? ?public Stack()
? ?
{
? ? ? ?this._array = Stack<T>._emptyArray;
? ? ? ?this._size = 0;
? ? ? ?this._version = 0;
? ?}

? ?[__DynamicallyInvokable]
? ?public Stack(int capacity)
? ?
{
? ? ? ?if (capacity < 0)
? ? ? ?{
? ? ? ? ? ?ThrowHelper.ThrowArgumentOutOfRangeException(
? ? ? ? ? ?ExceptionArgument.capacity,
? ? ? ? ? ?ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
? ? ? ?}
? ? ? ?this._array = new T[capacity];
? ? ? ?this._size = 0;
? ? ? ?this._version = 0;
? ?}

? ? ?
? ?[__DynamicallyInvokable]
? ?public void CopyTo(T[] array, int arrayIndex)
? ?
{
? ? ? ?if (array == null)
? ? ? ?{
? ? ? ? ? ?ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
? ? ? ?}
? ? ? ?if ((arrayIndex < 0) || (arrayIndex > array.Length))
? ? ? ?{
? ? ? ? ? ?ThrowHelper.ThrowArgumentOutOfRangeException(
? ? ? ? ? ?ExceptionArgument.arrayIndex,
? ? ? ? ? ?ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
? ? ? ?}
? ? ? ?if ((array.Length - arrayIndex) < this._size)
? ? ? ?{
? ? ? ? ? ?ThrowHelper.ThrowArgumentException(
? ? ? ? ? ?ExceptionResource.Argument_InvalidOffLen);
? ? ? ?}
? ? ? ?Array.Copy(this._array, 0, array, arrayIndex, this._size);
? ? ? ?Array.Reverse(array, arrayIndex, this._size);
? ?}


? ?[__DynamicallyInvokable]
? ?public T Pop()
? ?
{
? ? ? ?if (this._size == 0)
? ? ? ?{
? ? ? ? ? ?ThrowHelper.ThrowInvalidOperationException(
? ? ? ? ? ?ExceptionResource.InvalidOperation_EmptyStack);
? ? ? ?}
? ? ? ?this._version++;
? ? ? ?T local = this._array[--this._size];
? ? ? ?this._array[this._size] = default(T);
? ? ? ?return local;
? ?}

? ?[__DynamicallyInvokable]
? ?public void Push(T item)
? ?
{
? ? ? ?if (this._size == this._array.Length)
? ? ? ?{
? ? ? ? ? ?T[] destinationArray = new
? ? ? ? ? ?T[(this._array.Length == 0) ? 4 : (2 * this._array.Length)];
? ? ? ? ? ?Array.Copy(this._array, 0, destinationArray, 0, this._size);
? ? ? ? ? ?this._array = destinationArray;
? ? ? ?}
? ? ? ?this._array[this._size++] = item;
? ? ? ?this._version++;
? ?}

? ? ?
? ?// Properties
? ?[__DynamicallyInvokable]
? ?public int Count
? ?{
? ? ? ?[__DynamicallyInvokable,
? ? ? ?TargetedPatchingOptOut
? ? ? ?("Performance critical to inline this type of
? ? ? ? ? method across NGen image boundaries"
)]
? ? ? ?get
? ? ? ?{
? ? ? ? ? ?return this._size;
? ? ? ?}
? ?}

}

下面再看看Queue的實現:

[Serializable, DebuggerDisplay("Count = {Count}"), 
ComVisible(false),
DebuggerTypeProxy(typeof(System_QueueDebugView<>)),
__DynamicallyInvokable]
? ?public class Queue<T> : IEnumerable<T>,
? ? ? ? ? ? ICollection, IEnumerable
? ?{
? ? ? ?// Fields
? ? ? ?private T[] _array;
? ? ? ?private const int _DefaultCapacity = 4;
? ? ? ?private static T[] _emptyArray;
? ? ? ?private int _head;
? ? ? ?private int _size;
? ? ? ?private int _tail;
? ? ? ?private int _version;
? ? ? ?// Methods
? ? ? ?static Queue()
? ? ? ?
{
? ? ? ? ? ?Queue<T>._emptyArray = new T[0];
? ? ? ?}

? ? ? ?public Queue()
? ? ? ?
{
? ? ? ? ? ?this._array = Queue<T>._emptyArray;
? ? ? ?}

? ? ? ?public Queue(int capacity)
? ? ? ?
{
? ? ? ? ? ?if (capacity < 0)
? ? ? ? ? ?{
? ? ? ? ? ? ? ?ThrowHelper.ThrowArgumentOutOfRangeException(
? ? ? ? ? ? ? ?ExceptionArgument.capacity,
? ? ? ? ? ? ? ?ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
? ? ? ? ? ?}
? ? ? ? ? ?this._array = new T[capacity];
? ? ? ? ? ?this._head = 0;
? ? ? ? ? ?this._tail = 0;
? ? ? ? ? ?this._size = 0;
? ? ? ?}

? ? ? ?public T Dequeue()
? ? ? ?
{
? ? ? ? ? ?if (this._size == 0)
? ? ? ? ? ?{
? ? ? ? ? ? ? ?ThrowHelper.ThrowInvalidOperationException(
? ? ? ? ? ? ? ?ExceptionResource.InvalidOperation_EmptyQueue);
? ? ? ? ? ?}
? ? ? ? ? ?T local = this._array[this._head];
? ? ? ? ? ?this._array[this._head] = default(T);
? ? ? ? ? ?this._head = (this._head + 1) % this._array.Length;
? ? ? ? ? ?this._size--;
? ? ? ? ? ?this._version++;
? ? ? ? ? ?return local;
? ? ? ?}

? ? ? ?public void Enqueue(T item)
? ? ? ?
{
? ? ? ? ? ?if (this._size == this._array.Length)
? ? ? ? ? ?{
? ? ? ? ? ? ? ?int capacity = (int)((this._array.Length * 200L) / 100L);
? ? ? ? ? ? ? ?if (capacity < (this._array.Length + 4))
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?capacity = this._array.Length + 4;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?this.SetCapacity(capacity);
? ? ? ? ? ?}
? ? ? ? ? ?this._array[this._tail] = item;
? ? ? ? ? ?this._tail = (this._tail + 1) % this._array.Length;
? ? ? ? ? ?this._size++;
? ? ? ? ? ?this._version++;
? ? ? ?}

? ? ? ?private void SetCapacity(int capacity)
? ? ? ?
{
? ? ? ? ? ?T[] destinationArray = new T[capacity];
? ? ? ? ? ?if (this._size > 0)
? ? ? ? ? ?{
? ? ? ? ? ? ? ?if (this._head < this._tail)
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?Array.Copy(this._array, this._head,
? ? ? ? ? ? ? ? ? ?destinationArray, 0, this._size);
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?Array.Copy(this._array, this._head, destinationArray, 0,
? ? ? ? ? ? ? ? ? ?this._array.Length - this._head);
? ? ? ? ? ? ? ? ? ?Array.Copy(this._array, 0, destinationArray,
? ? ? ? ? ? ? ? ? ?this._array.Length - this._head, this._tail);
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ? ? ?this._array = destinationArray;
? ? ? ? ? ?this._head = 0;
? ? ? ? ? ?this._tail = (this._size == capacity) ? 0 : this._size;
? ? ? ? ? ?this._version++;
? ? ? ?}

? ? ? ?public int Count
? ? ? ?{
? ? ? ? ? ?[__DynamicallyInvokable, TargetedPatchingOptOut("Performance critical to
? ? ? ? ? ? ? inline this type of method across NGen image boundaries"
)]
? ? ? ? ? ?get
? ? ? ? ? ?{
? ? ? ? ? ? ? ?return this._size;
? ? ? ? ? ?}
? ? ? ?}
? ?}

可以看到.NET中Queue的實現也是基于數組的,定義了head和tail,當長度達到數組的容量的時候,使用了SetCapacity方法來進行擴容和拷貝。

4.?StackQueue的應用

Stack這種數據結構用途很廣泛,比如編譯器中的詞法分析器、Java虛擬機、軟件中的撤銷操作、瀏覽器中的回退操作,編譯器中的函數調用實現等等。

4.1 線程堆 (Thread Stack)

線程堆是操作系型系統分配的一塊內存區域。通常CPU上有一個特殊的稱之為堆指針的寄存器 (stack pointer) 。在程序初始化時,該指針指向棧頂,棧頂的地址最大。CPU有特殊的指令可以將值Push到線程堆上,以及將值Pop出堆棧。每一次Push操作都將值存放到堆指針指向的地方,并將堆指針遞減。每一次Pop都將堆指針指向的值從堆中移除,然后堆指針遞增,堆是向下增長的。Push到線程堆,以及從線程堆中Pop的值都存放到CPU的寄存器中。

當發起函數調用的時候,CPU使用特殊的指令將當前的指令指針(instruction pointer),如當前執行的代碼的地址壓入到堆上。然后CPU通過設置指令指針到函數調用的地址來跳轉到被調用的函數去執行。當函數返回值時,舊的指令指針從堆中Pop出來,然后從該指令地址之后繼續執行。

當進入到被調用的函數中時,堆指針減小來在堆上為函數中的局部變量分配更多的空間。如果函數中有一個32位的變量分配到了堆中,當函數返回時,堆指針就返回到之前的函數調用處,分配的空間就會被釋放。

如果函數有參數,這些參數會在函數調用之前就被分配在堆上,函數中的代碼可以從當前堆往上訪問到這些參數。

線程堆是一塊有一定限制的內存空間,如果調用了過多的嵌套函數,或者局部變量分配了過多的內存空間,就會產生堆棧溢出的錯誤。

下圖簡單顯示了線程堆的變化情況。

4.2 算術表達式的求值

Stack使用的一個最經典的例子就是算術表達式的求值了,這其中還包括前綴表達式和后綴表達式的求值。E. W. Dijkstra發明了使用兩個Stack,一個保存操作值,一個保存操作符的方法來實現表達式的求值,具體步驟如下:

1) 當輸入的是值的時候Push到屬于值的棧中。

2) 當輸入的是運算符的時候,Push到運算符的棧中。

3) 當遇到左括號的時候,忽略

4) 當遇到右括號的時候,Pop一個運算符,Pop兩個值,然后將計算結果Push到值的棧中。

下面是在C#中的一個簡單的括號表達式的求值:

/// <summary>
/// 一個簡單的表達式運算
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
? ?Stack<char> operation = new Stack<char>();
? ?Stack<Double> values = new Stack<double>();
? ?//為方便,直接使用ToChar對于兩位數的數組問題
? ?Char[] charArray = Console.ReadLine().ToCharArray();

? ?foreach (char s in charArray)
? ?{
? ? ? ?if (s.Equals('(')) { }
? ? ? ?else if (s.Equals('+')) operation.Push(s);
? ? ? ?else if (s.Equals('*')) operation.Push(s);
? ? ? ?else if (s.Equals(')'))
? ? ? ?{
? ? ? ? ? ?char op = operation.Pop();
? ? ? ? ? ?if (op.Equals('+'))
? ? ? ? ? ? ? ?values.Push(values.Pop() + values.Pop());
? ? ? ? ? ?else if (op.Equals('*'))
? ? ? ? ? ? ? ?values.Push(values.Pop() * values.Pop());
? ? ? ?}
? ? ? ?else values.Push(Double.Parse(s.ToString()));
? ?}
? ?Console.WriteLine(values.Pop());
? ?Console.ReadKey();

運行結果如下:

下圖演示了操作棧和數據棧的變化。

在編譯器技術中,前綴表達式,后綴表達式的求值都會用到堆。

4.3 Object-C中以及OpenGL中的圖形繪制

在Object-C以及OpenGL中都存在”繪圖上下文”,有時候我們對局部對象的繪圖不希望影響到全局的設置,所以需要保存上一次的繪圖狀態。下面是Object-C中繪制一個圓形的典型代碼:

- (void)drawGreenCircle:(CGContextRef)ctxt {
? ?UIGraphicsPushContext(ctxt);
? ?[[UIColor greenColor] setFill];
? ?// draw my circle
? ?UIGraphicsPopContext();
}

- (void)drawRect:(CGRect)aRect {
? ?CGContextRef context = UIGraphicsGetCurrentContext();
? ?[[UIColor redColor] setFill];
? ?// do some stuff
? ?[self drawGreenCircle:context];
? ?// do more stuff and expect fill color to be red
}

可以看到,在drawGreenCircle方法中,在設置填充顏色之前,我們Push保存了繪圖上下文的信息,然后在設置當前操作的一些環境變量,繪制圖形,繪制完成之后,我們Pop出之前保存的繪圖上下文信息,從而不影響后面的繪圖。

4.4 一些其他場景

有一個場景是利用stack 處理多余無效的請求,比如用戶長按鍵盤,或者在很短的時間內連續按某一個功能鍵,我們需要過濾到這些無效的請求。一個通常的做法是將所有的請求都壓入到堆中,然后要處理的時候Pop出來一個,這個就是最新的一次請求。

Queue的應用

在現實生活中Queue的應用也很廣泛,最廣泛的就是排隊了,”先來后到” First come first service ,以及Queue這個單詞就有排隊的意思。

還有,比如我們的播放器上的播放列表,我們的數據流對象,異步的數據傳輸結構(文件IO,管道通訊,套接字等)

還有一些解決對共享資源的沖突訪問,比如打印機的打印隊列等。消息隊列等。交通狀況模擬,呼叫中心用戶等待的時間的模擬等等。

5.?一點點感悟

本文簡單介紹了Stack和Queue的原理及實現,并介紹了一些應用。

最后一點點感悟就是不要為了使用數據結構而使用數據結構。舉個例子,之前看到過一個數組反轉的問題,剛學過Stack可能會想,這個簡單啊,直接將字符串挨個的Push進去,然后Pop出來就可以了,完美的解決方案。但是,這是不是最有效地呢,其實有更有效地方法,那就是以中間為對折,然后左右兩邊替換。

public static void Reverse(int[] array, int begin, int end)
{
? ?while (end > begin)
? ?{
? ? ? ?int temp = array[begin];
? ? ? ?array[begin] = array[end];
? ? ? ?array[end] = temp;

? ? ? ?begin++;
? ? ? ?end--;
? ?}
}


關注算法文摘,修煉開發內功


Copyright ? 2021 All Rights Reserved 版權所有 內丘陳奕迅音樂愛好組
哪里可以看成人片